1. 初始状态
    假设我们有一个这样的链表:
    null → 1 → 2 → 3 → 4 → 5 → null
    prev curr next
    我们只需要三个指针,分工非常清晰:
    prev:指向‌已经翻转好的部分的最后一个节点‌,初始是 null(因为最开始翻转部分是空)
    curr:指向‌当前要翻转的节点‌,初始是头节点 1
    next:用来‌提前保存下一个节点‌(不然后续翻转会断链,找不到下一个节点了)

  2. 第一步:翻转第一个节点
    1.‌先存下一个节点‌:next = curr.next → next 现在指向 2
    为什么要存?因为接下来我们要改 curr.next 的指向,不存就找不到原来的下一个节点了!
    2.翻转当前节点的指针‌:curr.next = prev → 原来 curr.next 指向 2,现在改成指向 prev(也就是 null)
    现在链表变成了:
    null ← 1 2 → 3 → 4 → 5 → null
    prev curr next
    3.两个指针往前走,准备翻转下一个‌:
    原来的 curr 已经翻转好了,所以 prev 移动到 curr 的位置:prev = curr
    curr 移动到刚才存的 next 位置:curr = next
    现在变成:
    null ← 1 2 → 3 → 4 → 5 → null
    prev curr

  3. 第二步:翻转第二个节点
    重复一模一样的步骤:
    1.存下一个:next = curr.next → next 指向 3
    2.翻转指针:curr.next = prev → 2 改成指向 1
    null ← 1 ← 2 3 → 4 → 5 → null
    prev curr next
    3.指针前移:
    prev = curr → prev 到 2
    curr = next → curr 到 3
    null ← 1 ← 2 3 → 4 → 5 → null
    prev curr

  4. 重复到最后,完成翻转
    一直重复这个过程,直到 curr 变成 null(所有节点都翻转完了),最终 prev 就指向翻转后的新头节点:
    null ← 1 ← 2 ← 3 ← 4 ← 5
    prev
    新头节点
    迭代法完整代码(Java,非常简洁)
    java

public ListNode reverseList(ListNode head)
 {
    ListNode prev = null;
    ListNode curr =head;
    while (curr != null
) {
        ListNode next = curr.next; // 1. 先存下一个节点
        curr.next = prev;          
// 2. 翻转当前指针
        prev = curr;               
// 3. 指针前移
        curr = next;
    }
    return
 prev;
}

💡 ‌记住口诀‌:存下一个,翻指针,往前走——永远不会错,核心就是‌一定要先存下一个,再改当前指针‌,顺序错了就会断链。

Logo

北京人形旗下天工造物具身智能开源社区,聚焦具身天工与慧思开物两大平台

更多推荐