力扣：206. 反转链表

反转链表，用迭代法进行操作，核心点是用一个临时变量存储交换，代码：

  1. public ListNode reverseList2(ListNode head) {
  2.     if (head == null || head.next == null) {
  3.         return head;
  4.     }
  6.     ListNode r = null;
  8.     while (head != null) {
  9.         // 临时变量
  10.         ListNode t = r;
  12.         r = head;
  13.         head = head.next;
  14.         r.next = t;
  15.     }
  17.     return r;
  18. }

递归有点绕，涉及到引用问题，先看代码：

  1. public ListNode reverseList(ListNode head) {
  2.     if(head.next == null){
  3.         return head;
  4.     }
  6.     ListNode tailNode = reverseList(head.next);
  7.     // 反正赋值
  8.     head.next.next = head;
  9.     // 清除回环
  10.     head.next =  null;
  12.     return tailNode;
  13. }

这里假设我们head传入的值是这样的：
5 -> 4 -> 3 -> 2 -> 1
那么：

  • 写递归先找到递归退出条件，第2行中，如果链表到尾部了，就退出，此时返回的head是 1；
  • 第6行中，递归返回一个 tailNode 节点，其实它是尾部节点，此时 tailNode=1, head = 2 -> 1；
  • 第8行中的head是倒数第二个节点，将它赋值给链表尾部，此时形成一个环形链表 head = 2 -> 1 -> 2 -> 1 …，tailNode = 1 -> 2 -> 1 -> 2 …
  • 第9行中将head.next = null,此时链表变为 head = 2，因为 head = 2 tailNode中要保留最小的一部分，所以 tailNode = 1 -> 2
  • 重复该步骤