GFG回文Linked List验证：反转后原链表仅打印一个节点，求错因

我在GFG练习平台写代码验证链表是否为回文，测试链表是1->2->1。调用反转链表方法后，遍历原链表只输出一个节点；但注释掉反转的代码后，遍历输出正常。

原代码如下：

class Solution
{
    //Function to check whether the list is palindrome.
    boolean isPalindrome(Node head) 
    {
        Node temp=head;
        Node reversed= reverseList(temp);
        Node cur = head;
        
        while(cur!=null)
        {
            System.out.println(cur.data+"    inloop");
            cur=cur.next;
        }
         
        return true;
    } 

    Node reverseList(Node node)
    {        
        Node prev = null;
        Node current = node;
        Node next = null;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        node = prev;
        return node; 
    }
}

现象 #

• 调用reverseList(temp)后，输出仅为：

  1    inloop
  

• 注释掉Node reversed= reverseList(temp);后，输出符合预期：

  1    inloop
  2    inloop
  1    inloop
  

错误原因 #

Java里对象是引用传递，temp只是head的引用副本，指向的是同一个链表节点对象。在reverseList方法中，第一个循环就把原链表首节点（也就是head指向的节点）的next改成了null——因为初始prev是null，执行current.next = prev时，原链表的第一个节点就和后面的节点断开了。所以后续遍历head时，只能走到第一个节点就结束。

修正思路 #

要避免修改原链表，有两种常见方案：

• 方案1：反转前先复制整个链表，再对复制后的链表进行反转操作，这样原链表的结构不会被破坏。
• 方案2：用快慢指针找到链表的中间节点，只反转链表的后半部分，这样既不影响原链表前半部分，还能节省空间（不需要复制整个链表），这也是验证回文链表的最优解法之一。

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