java - LeetCode - LeetCode提交通过，但在IDE中返回null的解决方案

Question

问题链接:https://leetcode.com/problems/intersection-of-two-linked-lists/

这个问题是关于获取两个单独的链表的交集，我有一个解决方案，将一个链表中的所有节点放入一个ArrayList中，然后检查另一个链表中的节点是否包含在ArrayList中或不是。该解决方案通过了 LeetCode 提交，但不知何故在我的 IDE 中仅返回 null。我尝试了测试用例的变体，但全部返回 null。这是问题的简短解决方案和我的测试用例之一。

class ListNode {
    int val;
    ListNode next;
    ListNode(int x){
        this.val = x;
        this.next = null;
    }
}

class Solution {
    public ListNode getIntersectionNodeUsingArrayList(ListNode headA, ListNode headB) {
        List<ListNode> list = new ArrayList<ListNode>();

        while(headA != null) {
            list.add(headA);
            headA = headA.next;
        }

        while(headB != null) {
            if(list.contains(headB)) {
                return headB;
            }

            headB = headB.next;
        }

        return null;
    }
public class TwoLL {

    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode listA0 = new ListNode(4);
        listA0.next = new ListNode(1);
        listA0.next.next = new ListNode(8);
        listA0.next.next.next = new ListNode(4);
        listA0.next.next.next.next = new ListNode(5);

        ListNode listB0 = new ListNode(5);
        listB0.next = new ListNode(0);
        listB0.next.next = new ListNode(1);
        listB0.next.next.next = new ListNode(8);
        listB0.next.next.next.next = new ListNode(4);
        listB0.next.next.next.next.next = new ListNode(5);

        ListNode result = sol.getIntersectionNodeUsingArrayList(listA0, listB0);

        System.out.println(result.val); // should be 8 but it returns NPE since result is null.
        System.out.println(result); // returns null as well, instead of the memory address of the node 

任何帮助将不胜感激!

Answer 1

您构建列表的方式不会在它们之间产生交集。属于两个列表的节点是分开的，没有交集。

listA0 4   ->  1  ->  8 -> 4 -> 5
listB0 5 -> 0 -> 1 -> 8 -> 4 -> 5

在上面，节点 8、4、5 是不同的 ListNode 实例。因此，它们不可能相等。

尝试将公共(public)节点添加到列表中

ListNode common = new ListNode(10);
listA0.next.next.next.next.next = common;
listB0.next.next.next.next.next.next = common;

这会将结果打印为10。

为了模拟您提到的情况，下面的代码应该可以工作

ListNode common  = new ListNode(8);
common.next = new ListNode(4);
common.next.next = new ListNode(5);

ListNode listA0 = new ListNode(4);
listA0.next = new ListNode(1);
listA0.next.next = common;


ListNode listB0 = new ListNode(5);
listB0.next = new ListNode(0);
listB0.next.next = new ListNode(1);
listB0.next.next.next = common;