java - 使用 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
  • 不过现在 Stack 是:3 - 2 - 4(你覆盖了 head 中的值)
• 下一个元素
  • 新名单:4 - 3
  • 堆栈:3 - 4(您覆盖了第二个列表节点中的值)
• 下一个元素
  • 新名单:4 - 3 - 3
  • 堆栈:4
• 最后一个元素
  • 新名单:4 - 3 - 3 - 4

如何让它发挥作用？

几种可能的修复方法:

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