linked-list - 反转链表时遇到问题

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;
        
        
    }
}

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

标签： linked-listreverse

Answer 1

发生这种情况是因为你已经改变cur.next了分配newHead.next=prev;，使之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
}