LeetCode回文链表：反转全链表失效，半链表正常？求解析

问题核心原因拆解 #

• 反转整个链表的致命问题
  你执行ListNode slow=reverse(head);时，链表是引用类型，反转函数会直接修改原链表的节点指针关系。反转完成后，原链表的头节点head的next会被置为null（因为原头节点变成了反转后的尾节点）。这时候fast=head去遍历的话，只能走一步就到null，后续的节点对比根本无法完整执行，自然会得到错误结果。

  举个实际例子：原链表是1->2->3->2->1，反转整个链表后，原head（值为1的节点）的next变为null，slow指向反转后的新头（值为1的原尾节点）。对比时第一次两个节点值相等，之后fast=fast.next变成null，循环直接结束返回true——哪怕原链表不是回文（比如1->2->3->4），也会错误返回true，因为只对比了第一个节点。

• 反转半链表能正常运行的逻辑
  双指针法中，你先通过快慢指针找到链表中点，此时slow指向后半段的起点。反转slow时，修改的只是后半段链表的指针，原链表的前半段完全不受影响。之后fast=head指向完整的前半段，slow指向反转后的后半段，两者是独立的链表部分，遍历对比时不会互相干扰，能完整检查每一对对应节点的值是否相等，所以可以正确判断回文。

你的代码对比 #

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast=head;
        ListNode slow=reverse(head); // 这里反转整个链表会破坏原链表结构
        // 下面是双指针法的正确逻辑（注释部分）
        // while(fast!=null && fast.next!=null){
        //     fast=fast.next.next;
        //     slow=slow.next;
        // }
        // slow=reverse(slow); // 只反转后半段，不影响前半段
        // fast=head;
        while(slow!=null){
            if(fast.val!=slow.val){
                return false;
            }
            fast=fast.next;
            slow=slow.next;
        }
        return true;
    }
    public ListNode reverse(ListNode head){
        ListNode prev=null;
        ListNode cur=head;
        ListNode ne=head.next;
        while(cur!=null){
            cur.next=prev;
            prev=cur;
            cur=ne;
            if(ne!=null){
                ne=ne.next;
            }
        }
        return prev;
    }
}

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