java - 我执行 "Intersection of Two Linked Lists"的错误在哪里？

Question

我正在 Leet Code 准备算法测试，这里是 N°160 Intersection of Two Linked Lists 的描述:

编写一个程序，找出两个单向链表的交集开始的节点。

例如下面两个链表:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

在节点 c1 处开始相交。

注意事项:

• 如果两个链表根本没有交集，则返回null。
• 链表必须在函数返回后保持其原始结构。
• 您可以假设整个链接结构中的任何地方都没有循环。
• 您的代码应该最好在 O(n) 时间内运行并且仅使用 O(1) 内存。

---

然后我写了一个Java程序来解决。它通过了 39/42 个测试用例，然后在测试 39 时失败了。我研究了一个多小时也没有找到错误行。有人可以帮助我吗？

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Stack<Integer> stackA = new Stack<>();
        Stack<Integer> stackB = new Stack<>();
        ListNode pointerA = headA;
        ListNode pointerB = headB;
        while (pointerA != null) {
            stackA.push(pointerA.val);
            pointerA = pointerA.next;
        }
        while (pointerB != null) {
            stackB.push(pointerB.val);
            pointerB = pointerB.next;
        }

        // find the common part between A & B, then build the comment node
        ListNode intersect = null;
        while (!stackA.empty() && !stackB.empty() && stackA.peek() == stackB.peek()) {
            ListNode newHead = new ListNode(stackA.peek());
            newHead.next = intersect;
            intersect = newHead;
            stackA.pop();
            stackB.pop();
        }
        return intersect;
    }
}

Submission Result: Wrong Answer

• Input: Intersected at '10000':
  • [1,3,5,7,9,...,9991,9993,9995,9997,9999,10000]
  • [2,4,6,8,10,...,9990,9992,9994,9996,9998,10000]
• Output: No intersection
• Expected: Intersected at '10000'

我知道有更好的算法来处理这个测试，但在这篇文章中，我只想找出哪一行是错的。

Answer 1

Stack 数据结构使用对象Integer 而不是原始类型int。所以我需要将比较更改为

stackA.peek().equals(stackB.peek())

这次提交被接受了。

现在如果你对这个算法测试感兴趣，你可以在the LeetCode forum中找到更好的解决方案。或 Program Creek由 danh 提供。