判断回文LinkedList时head被修改的原因及解决方法求助

问题原因 #

你遇到的核心问题是单链表的反转操作是原地修改链表节点的引用关系，而非创建新链表。Java中对象引用的传递是「按值传递」，但传递的是引用的副本——也就是说，你传入head到反转方法时，方法内的curr变量和外部的head指向堆内存中同一个ListNode对象。当你执行curr.next = prev这类操作时，直接修改了堆里原链表节点的next属性，外部的head指向的节点自然会受到影响，最终原链表的结构被彻底改变，head也就变成了反转后的链表尾节点。

看你当前的代码，第一次while循环已经把整个原链表原地反转了：原head节点的next被设为null，变成了链表的最后一个节点，所以后续用curr = head去比较时，只能拿到第一个节点就结束，完全无法正确判断回文。

解决思路 #

不要直接反转整个原链表，而是只反转链表的后半部分，并且不破坏原链表的前半部分结构。具体步骤：

• 用快慢指针找到链表的中间节点；
• 反转中间节点之后的后半段链表；
• 同时遍历原链表的前半段和反转后的后半段，比较节点值是否一致；
• （可选）如果需要保留原链表结构，比较完成后再把后半段反转回来。

修正后的代码 #

/**
 * Definition for singly-linked list.
 * 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 boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        
        // 快慢指针找中间节点
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // 反转后半段链表
        ListNode reversedHalf = reverse(slow.next);
        
        // 比较前半段和反转后的后半段
        ListNode p1 = head;
        ListNode p2 = reversedHalf;
        boolean isPalin = true;
        while (isPalin && p2 != null) {
            if (p1.val != p2.val) {
                isPalin = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        
        // 可选：恢复原链表结构
        slow.next = reverse(reversedHalf);
        
        return isPalin;
    }
    
    // 反转链表的方法，返回反转后的头节点，不影响原链表的前半部分
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }
}

这段代码中，reverse方法只处理传入的后半段链表，原链表的前半段结构完全不受影响，head指针也不会被修改到末尾。比较完成后还可以把后半段反转回去，保证原链表结构不变。

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