反转链接列表时遇到问题

Question

我正在尝试使用java和下面的代码来反向链表。

class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur=head,prev=null,newHead=null;

while(cur!=null)
{
newHead=cur;
newHead.next=prev;
prev=newHead;
System.out.println(1);
cur=cur.next;

}

return newHead;


}
}

我不明白为什么循环在这里只执行一次。我做错什么了吗？

Answer 1

之所以会发生这种情况，是因为您用赋值newHead.next=prev;更改了cur.next，使其成为null。意识到newHead在那个时刻引用了与cur相同的对象。

在发生此更改之前，您应该保存cur.next的原始值：

ListNode cur = head, prev = null, newHead = null, next;

while (cur != null)
{
newHead = cur;
next = cur.next; // <--- save original value of `cur.next`
newHead.next = prev;
prev = newHead;
cur = next;  // <--- use that original value here
}