JavaScript 打印链表逆序而不实际反转

链表是一种线性数据结构，其内存不以连续方式排列。我们将使用不同的方法和示例来编写JavaScript的完整代码，以更好地理解这个过程。

问题简介

在给定的问题中，我们给出一个链表，我们需要按照逆序打印它的所有元素，但是我们不需要反转给定的链表。

例如 –

Given linked list: 1 2 3 4 5 6
Result: 6 5 4 3 2 1

我们将使用两种方法以相反的方式打印给定的链表，让我们看看它们-

存储在数组中

在这种方法中，我们将按照链表中它们的顺序存储给定链表的元素，然后我们将以相反的顺序打印数组的元素，因为获取数组的索引很容易。

示例

由于数组具有固定的大小, 我们假设链表中元素的最大数量为1000, 因此我们只创建这个大小的数组。让我们来看看代码 –

<html>
<body>
   <script>
      // creating class for linked list 
      class Node {
         constructor(data){
            this.value = data
            this.next = null
         }
      }
      // function to print elements of the linked list 
      function print(head){
         var temp = head
         while(temp != null) {
            document.write(temp.value + " ")
            temp = temp.next
         }
      }
      // function to print the elements in an opposite manner 
      function reverse_LL(head) {
         var temp = head;
         // getting the size of the linked list 
         count = 0;
         while(temp != null){
            temp = temp.next
            count++;
         }
         var arr = new Array(count)
         temp = head;
         var i = 0
         while(temp != null){
            arr[i] = temp.value
            temp = temp.next
            i++
         }
         while(i--) {
            document.write(arr[i] + " ")
         }
      }
      // creating the linked list 
      var head = new Node(1)
      head.next = new Node(2)
      head.next.next = new Node(3)
      head.next.next.next = new Node(4)
      head.next.next.next.next = new Node(5)
      head.next.next.next.next.next = new Node(6)
      // printing the linked list 
      document.write("The linked list is: ")
      print(head)
      document.write("<br>The linked list in reverse order is: ")
      reverse_LL(head)
   </script>
</body>
</html>

时间和空间复杂度

上述代码的时间复杂度为O(N)，其中N是链表的大小。

上述代码的空间复杂度为O(N)，因为我们使用了额外的数组来存储链表的元素。

注意：在上述代码中，我们没有将数组大小设置为1000，而是首先遍历链表以找到其大小，然后创建一个相同大小的数组。

使用递归

在上述方法中，我们首先找到链表的大小，然后使用数组来存储元素，这使得代码看起来更长。为了解决这个问题，我们可以使用递归的概念，其中我们将创建一个函数并将链表作为参数传递。

在递归函数中，我们将使用基本情况，即当前参数为null，否则我们将首先用下一个相同的函数调用下一个节点作为参数，然后调用后，我们将打印当前节点的值。

示例

这将以相反的方式打印链表的元素，而不需要翻转给定的链表，让我们看下代码−

<html>
<body>
   <script>
      // creating class for linked list 
      class Node{
         constructor(data){
            this.value = data
            this.next = null
         }
      }

      // function to print elements of the linked list 
      function print(head){
         var temp = head
         while(temp != null){
            document.write(temp.value + " ")
            temp = temp.next
         }
      }

      // function to print the elements in the oposite manner 
      function reverse_LL(head){
         if(head == null)    {
            return 
         }
         reverse_LL(head.next)
         document.write(head.value + " ")
      }

      // creating the linked list 
      var head = new Node(1)
      head.next = new Node(2)
      head.next.next = new Node(3)
      head.next.next.next = new Node(4)
      head.next.next.next.next = new Node(5)
      head.next.next.next.next.next = new Node(6) 

      // printing the linked list 
      document.write("The linked list is: ")
      print(head)
      document.write("<br>The linked list in reverse order is: ")
      reverse_LL(head)
   </script>
</body>
</html>