反转链表逻辑疑问：为何pre需赋值为cur而非pre.next？

题目背景 #

给定单链表的head，反转链表并返回反转后的链表。ListNode类定义如下：

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

我的错误代码 #

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head != null) {
            ListNode pre = head;
            ListNode cur = head.next;
            ListNode temp;
            while (cur != null) {
                temp = cur.next;
                cur.next = pre; 
                pre = pre.next; // 此处应改为pre = cur; 但我不理解原因
                cur = temp;
            }
            head.next = null;
            return pre;
        } else {
            return null;
        }
    }
}

我的疑问 #

要让代码正常运行，需将循环内的pre = pre.next;改为pre = cur;，但我完全不理解原因。执行temp = cur.next;后，pre应该仍指向cur，对吗？请问问题出在哪里？能否详细解释？

问题拆解与解释 #

咱们拿具体链表例子一步步走，就能明白问题所在：
假设初始链表是 1 -> 2 -> 3 -> null，初始时pre指向节点1，cur指向节点2。

错误代码的执行流程 #

1. 第一次循环：

   • temp = cur.next; → temp保存节点3的引用
   • cur.next = pre; → 节点2的next改为指向节点1，此时链表变成 1 <-> 2 -> 3 -> null（节点1的next还是节点2，节点2的next变成节点1）
   • pre = pre.next; → pre原本指向节点1，pre.next是节点2，所以pre现在指向节点2
   • cur = temp; → cur指向节点3

2. 第二次循环：

   • temp = cur.next; → temp保存null
   • cur.next = pre; → 节点3的next改为指向节点2，此时链表变成 1 <-> 2 <-> 3 -> null
   • pre = pre.next; → pre现在指向节点2，pre.next是节点1，所以pre变成指向节点1
   • cur = temp; → cur变成null，循环结束

3. 最后操作：head.next = null; → 节点1的next设为null，链表变成 1 <- 2 <- 3，但返回的pre是节点1，这明显不是反转后的头节点（正确头应该是3）。

正确逻辑的核心 #

在迭代反转链表的逻辑里，pre的角色是已经完成反转的链表部分的头节点，cur是当前正要反转的节点。每完成一次cur.next = pre的反转操作后，cur就变成了新的反转链表的头，所以pre必须直接更新为cur，而不是去取pre.next——因为pre.next此时指向的是反转前的节点，完全不是我们需要的新头部。

正确代码的执行流程 #

把pre = pre.next;改成pre = cur;后，重新走一遍：

1. 第一次循环：

   • temp = cur.next; → temp保存节点3
   • cur.next = pre; → 节点2指向节点1
   • pre = cur; → pre更新为节点2（现在反转后的部分是2 -> 1）
   • cur = temp; → cur指向节点3

2. 第二次循环：

   • temp = cur.next; → temp保存null
   • cur.next = pre; → 节点3指向节点2
   • pre = cur; → pre更新为节点3（现在反转后的部分是3 -> 2 -> 1）
   • cur = temp; → cur变成null，循环结束

3. 最后head.next = null;把节点1的next设为null，返回pre（节点3），这就是正确的反转链表头。

误解点澄清 #

你以为执行temp = cur.next;后pre指向cur？这是混淆了节点的next属性和变量的引用：

• pre是一个变量，它存储的是节点的内存地址，初始时pre存储节点1的地址，指向节点1；cur存储节点2的地址，指向节点2。
• temp = cur.next;只是把节点2的next属性值（节点3的地址）存到temp里，完全不会改变pre的指向，pre还是指向节点1。
• 只有直接给pre赋值（比如pre = cur），才会让pre的存储地址变成节点2的地址，也就是指向节点2。

内容的提问来源于stack exchange，提问作者leavejimmyalone