8.7 剑指刷完隔了几周，迭代法和递归法都突然不熟悉了！明天继续做！
8.8 可以一次 AC
8.9 可以一次 AC

第一次复习
9.14 可以 AC

题目描述

力扣：https://leetcode-cn.com/problems/reverse-linked-list/submissions/

剑指：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

解题思路：迭代 / 递归

K神题解：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/solution/

1. 迭代（双指针 + 暂存指针）

  • 迭代法首先要立刻想到 pre 和 cur 都要向前移动
  • pre 向前移动可以依赖 cur
  • 但是 cur 向前移动只能依靠 cur 自己的 cur.next
  • 但是 cur.next 是要反指向 pre 的
  • 所以第一步一定要先把 cur.next 暂存起来
  • 迭代法公式：暂存 —> 反指 —> 前移
  • 初始化：pre 为 null，cur 为 head
    1. class Solution {
    2.   public ListNode reverseList(ListNode head) {
    3.       ListNode pre = null, cur = head;
    4.       while(cur != null) {
    5.           ListNode tmp = cur.next; // 先暂存 cur.next 方便后续 cur 反指向 pre 后还能往前移动
    6.           cur.next = pre; // cur 反指向 pre
    7.           pre = cur; // pre 先往前移动
    8.           cur = tmp; // cur 再根据刚刚暂存起来的 cur.next 往前移动
    9.       }
    10.       return pre;
    11.   }
    12. }

2. 递归回溯（空间复杂度比迭代要高，因为递归要用到栈）

  • 因为反转链表这题最后是要返回反转链表后的头节点，所以递归法的核心，或者说递归的目的是：一直向下递归直到取得反转链表后的头节点然后一直回溯直到返回给最上层。
  • 又因为反转链表得涉及到两个节点的操作，而原方法只有一个参数，不好进行递归反转操作，所以只得再创建一个递归方法，传进 pre 与 cur ，第一次传进去的 pre 为 null，cur 为 head。
  • 所以反转链表递归回溯法的思路是：递归到最后取到反转链表后的头节点作为每次递归的返回值；回溯时一做反指操作，二做返回反转链表后的头节点的操作。

  • 反转链表递归回溯三部曲：

    • 终止条件：返回反转链表头节点
    • 递归：维护好每次递归返回的反转链表头节点

    • 回溯：1. 反指 —> 2. 向上回溯递归回来的头节点

      1. class Solution {
      2. public ListNode reverseList(ListNode head) {
      3.    return recur(null, head);
      4. }
      6. public ListNode recur(ListNode pre, ListNode cur) {
      7.    if(cur == null) return pre; // 递归终止条件返回的其实就是反转链表后的头节点
      8.                                // 所以下面要记得保存起来，回溯的时候要向上返回
      9.    ListNode res = recur(cur, cur.next); // 递归，结束记得保存反转链表后的头节点
      10.    cur.next =pre; // 回溯时反指
      11.    return res; // 回溯时返回反转链表后的头节点
      12. }
      13. }