使用 next 方法时，链表无法正确迭代 while 循环

Question

我正在尝试使用堆栈迭代地反转链表。我已经确定了问题发生的位置，但是对于我来说，无法弄清楚为什么当我调用 ListNode 的 next 方法时代码没有正确迭代。我已经在下面的代码中标记了错误发生的地方。

这是我运行代码时的结果：

Before: 1->2->3->4->null
After: 4->3->3->4->null

结果应该是这样的：

Before: 1->2->3->4->null
After: 4->3->2->1->null

任何人都可以指出我正在发生的事情的正确方向吗？谢谢！

代码如下：

public class Solution {
    public static void main(String[] args) {
        private static Solution soln = new Solution();
        ListNode head = makeLinkedList(4);

        System.out.print("Before: ");
        printLinkedList(head);
        System.out.println();

        soln.reverseList(head);

        System.out.print(" After: ");
        printLinkedList(head);

        System.exit(0);
    }

    public ListNode reverseList(ListNode head) {
        Stack<ListNode> listContents = new Stack<ListNode>();

        // iterate list and add to stack
        ListNode tmp = head;
        while (tmp != null) {
            listContents.push(tmp);
            tmp = tmp.next;
        }

        // iterate list again and replace each val with stack val
        tmp = head;
        while (tmp != null) {
            tmp.val = listContents.pop().val;
            // this is where the code seems to fail
            tmp = tmp.next; 
        }
        return head;
    }
}

ListNode 的定义方式：

public class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int item) { 
        val = item; 
    }
}

下面是我创建链表的方法：

private static ListNode makeLinkedList(int numNodes) {
    ListNode head = null;
    ListNode tmp = null;
    for (int i = 1; i < numNodes + 1; i++) {
        if (tmp == null) {
            tmp = new ListNode(i);
            head = tmp;
        } else {
            tmp.next = new ListNode(i);
            tmp = tmp.next;
        }
    }
    return head;
}

辅助方法：

private static void printLinkedList(ListNode head) {
    ListNode tmp = head;
    while (tmp != null) {
        System.out.print(tmp.val + "->");
        tmp = tmp.next;
    }
    System.out.print("null");
}

Answer 1

为什么不起作用？

问题是您将 ListNode 存储在 Stack 中，而不仅仅是值。这样，您将覆盖您正在阅读的节点的值：

你从堆栈开始（顶部在前）：4 - 3 - 2 - 1
你取前头，出栈，写入值
- 新列表：4
- 堆栈但是现在是：3 - 2 - 4（你覆盖了头部的值）
下一个元素
- 新列表：4 - 3
- 堆栈：3 - 4（您覆盖了第二个列表节点中的值）
下一个元素
- 新列表：4 - 3 - 3
- 堆栈：4
最后一个元素
- 新列表：4 - 3 - 3 - 4

如何让它发挥作用？

几种可能的修复方法：

仅将值存储在堆栈中。
为反向列表创建新的 ListNode。
重新连接节点而不是重写它们的值。请注意，这甚至可以在不使用 Stack 的情况下完成 - 请参阅@xenteros 的回答。

Answer 2

如果可能，应该通过反转 links 来反转 linked 列表。我会尝试以下操作：

public static ListNode reverseList(ListNode head) {
    // iterate list and add to stack
    ListNode current = head;
    ListNode previous = null;
    ListNode temp = null;
    while (current.next != null) {
        temp = previous;
        previous = current;
        current = current.next;
        previous.next = temp;
    }
    current.next = previous;
    return current;
}

它return是个新头。用法示例：

public static void main(String[] args) {

    ListNode head = makeLinkedList(4);

    System.out.print("Before: ");
    printLinkedList(head);
    System.out.println();

    head = reverseList(head);

    System.out.print(" After: ");
    printLinkedList(head);

    System.exit(0);
}

>>Before: 1->2->3->4->null
>>After: 4->3->2->1->null
>>Process finished with exit code 0

算法描述为：对于列表中的每个节点，不是 link 下一个元素，而是 link 前一个元素和 return 最后一个元素作为头。

Answer 3

发生这种情况是因为您在不知情的情况下更改了 LinkedList。换句话说，当您覆盖 LinkedList 中任何 more 的值时，您之前压入堆栈的节点也会被修改。因此，确保这种情况不会发生的一种方法是在堆栈上实例化并推送一个新节点（副本）：

public ListNode reverseList(ListNode head) {
 Stack<ListNode> listContents = new Stack<ListNode>();

 // iterate list and add to stack
 ListNode tmp = head;

 while (tmp != null) {
     ListNode newNode = new ListNode(temp);
     listContents.push(newNode);
     tmp = tmp.next;
 }

 // iterate list again and replace each val with stack val
 tmp = head;
 while (tmp != null) {
     tmp.val = listContents.pop().val;
     tmp = tmp.next; 
 }
 return head;
}

简单修改ListNode class添加复制构造函数：

public class ListNode {
  int val;
  ListNode next = null;

  public ListNode (ListNode that){
     this.val = that.val;
      this.next = null;     //Could be that.next
   }

  public ListNode(int item) { 
      val = item; 
  }
}

使用 next 方法时，链表无法正确迭代 while 循环

Linked List does not iterate in while loop correctly when using next method

java

stack

reverse

linked-list

为什么不起作用？

如何让它发挥作用？