反向链表只打印为一个节点

Question

我正在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; 
}
}

此代码的输出是(传递的链表是1->2->1): -

1    inloop

但是如果我注释掉Node reversed = reverseList(temp);行，输出如预期的那样:-

1    inloop
2    inloop
1    inloop

我错在哪里?

Answer 1

当列表被反转时，先前的列表头部已成为尾部。具体地说，在反转之后，head引用现在反转的列表的尾部。尾巴(根据定义)有一个next成员null，所以你的while循环只迭代一次。

请注意，当您反转列表时，您不再拥有原始顺序:所有next成员都失去了其原始值，现在(只有)有一个反映反转顺序的引用。

你有几个选择来做正确的:

1. 让你的reverse方法创建一个新的列表，这样调用者将同时拥有原始列表和反向列表。这将允许您串联迭代两个列表并按预期比较节点值

2. 从列表中创建数组。现在检查该数组是否为回文。

3. 以上选项需要O(n)个额外空间。不用O(n)也可以解出来辅助空格:仅反转一半在列表中。这里不需要创建新节点，只需对列表的一半进行反转，就可以同时遍历反转部分和非反转部分，并进行值比较