反转链表

---

题目：

解题：

1、时间复杂度为O(n)的复杂方法

• 使用栈切换顺序，然后存入另一个ListNode，输出

  class Solution {
      public ListNode head1;
      public ListNode reverseList(ListNode head) {
          LinkedList<Integer> stack = null;
              stack = new LinkedList<Integer>();
              while (!(head == null)) {
                  stack.push(head.val);
                  head = head.next;
              }
          int size = stack.size();
          for (int i = 0; i < size; i++) {
                  ListNode node = new ListNode(stack.pop());
  
                  if (this.head1 == null) {
                      this.head1 = node;
                  } else {
                      ListNode cur = this.head1;
                      while (cur.next != null) {
                          cur = cur.next;
                      }
                      cur.next = node;
                  }
              }
              return this.head1;
      }
  
      
  }

• 使用递归实现,然后存入另一个ListNode，输出

  class Solution2 {
  
      ArrayList<Integer> tmp = new ArrayList<>();
      public ListNode head1;
      public ListNode reverseList(ListNode head) {
          recur(head);
  
          for (int i = 0; i < tmp.size(); i++) {
              ListNode node = new ListNode(tmp.get(i));
  
              if (this.head1 == null) {
                  this.head1 = node;
              } else {
                  ListNode cur = this.head1;
                  while (cur.next != null) {
                      cur = cur.next;
                  }
                  cur.next = node;
              }
          }
          return this.head1;
      }
  
      void recur(ListNode head) {
          if (head == null) return;
          recur(head.next);
          tmp.add(head.val);
      }
  
  }

2、时间复杂度为O(n)的优化解法

• 使用迭代（双指针）

  • 时间复杂度 O(N) ： 遍历链表使用线性大小时间。

  • 空间复杂度 O(1) ： 变量 pre 和 cur 使用常数大小额外空间。

  • 解题思路：

    • 
    • 
    • 
    • 
    • 
    • 
    • 
    • 
    • 
    • 
    • 
    • 

  • 代码：

    class Solution3 {
    
        public ListNode reverseList(ListNode head) {
            ListNode prev = null;
            ListNode cur = head;
            while(cur != null) {
                ListNode nextNode = cur.next;
                cur.next = prev;
                prev = cur;
                cur = nextNode;
            }
            return prev;
        }
    
    }

• 使用递归，时间复杂度O(n)

  • **时间复杂度：O(n)**，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。

  • **空间复杂度：O(n)**，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n层。

  • 解题思路：

    • 

  • 代码：

    class Solution4 {
        public ListNode reverseList(ListNode head) {
    
            if (head == null || head.next == null) {
                return head;
            }
    
            ListNode newHead = reverseList(head.next);
            head.next.next = head;
            head.next = null;
            return newHead;
        }
    }