反转有序链表时最后一个元素丢失、输出循环重复问题排查求助

问题根因 #

你的代码存在两个核心错误：

• 反转链表完成后，没有更新类的head成员变量为新的头节点prev，后续所有遍历、再次反转操作还是基于旧的头节点执行，逻辑完全错乱
• 方法仅返回新头节点的数据，不能支撑完整链表的遍历需求，反复调用该方法时，会在被截断的链表上反复修改节点指针，最终形成环形链表，导致循环打印重复内容

如果你使用的是带哨兵（哑）节点的链表设计（head本身不存储实际数据，第一个有效数据存于head.next），还存在第三个错误：反转起点错设为head本身，而非第一个有效节点head.next。

修复方案 #

方案1：head为存储有效数据的普通头节点 #

// 方法可返回新头节点，也可设为void，核心是更新内部head
public Node reverseList() {
    if (head == null || head.next == null) { 
        return head;                    
    }

    Node prev = null;
    Node current = head;
    Node next = null;
    while (current != null) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    // *关键：更新类的head成员为新的头节点*
    head = prev;
    return head;
}

需要打印反转后的链表时，调用reverseList后从head开始遍历所有节点即可。

方案2：head为不存数据的哨兵节点 #

public Node reverseList() {
    if (head.next == null) { 
        return head;                    
    }

    Node prev = null;
    Node current = head.next; // 从第一个有效节点开始反转
    Node next = null;
    while (current != null) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    // *关键：将哨兵节点的next指向新的第一个有效节点*
    head.next = prev;
    return head;
}

需要打印反转后的链表时，调用reverseList后从head.next开始遍历所有节点即可。

测试现象解释 #

你的测试用例升序排列后链表为1→2→3，head指向1：

• 第一次调用原reverseList：反转后节点指向变为3→2→1→null，方法返回新头节点的值3，但head仍指向旧头1。此时如果打印逻辑先取返回值3，再从head=1开始遍历只能拿到1，最终输出就会出现缺值、错值的情况
• 多次调用原方法时，基于旧头节点反复修改指针，很容易形成两个节点互相指向的环形结构，就会出现3,1,3,1...的循环输出

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