从两个相交链表中找到相交点。

Suppose there are two singly linked lists both of which intersect at some point and become a single linked list.

假设有两个单独的链表，它们在某个点相交并成为一个链表。

The head or start pointers of both the lists are known, but the intersecting node is not known. Also, the number of nodes in each of the list before they intersect are unknown and both list may have it different i.e. List1 may have n nodes before it reaches intersection point and List2 might have m nodes before it reaches intersection point where m and n may be

两个列表的头或开始指针都是已知的，但是交叉节点是未知的。此外，在它们相交之前，每个列表中的节点数都是未知的，并且两个列表可能有不同的含义，即List1在到达交点之前可能有n个节点，而List2可能在达到m和n的相交点之前有m个节点。

m = n,
m = n,
m < n or
m < n或
m > n
m > n

One known or easy solution is to compare every node pointer in the first list with every other node pointer in the second list by which the matching node pointers will lead us to the intersecting node. But, the time complexity in this case will O(n²) which will be high.

一个已知或简单的解决方案是将第一个列表中的每个节点指针与第二个列表中的每个节点指针进行比较，在第二个列表中，匹配的节点指针将引导我们到达交叉节点。但是，这种情况下的时间复杂度是O(n2)高。

What is the most efficient way of finding the intersecting node?

找到相交点的最有效的方法是什么?

6 个解决方案

#1

This takes O(M+N) time and O(1) space, where M and N are the total length of the linked lists. Maybe inefficient if the common part is very long (i.e. M,N >> m,n)

这需要O(M+N)时间和O(1)空间，其中M和N是链表的总长度。如果公共部分很长(比如M,N >> M,N)，效率可能会很低

Traverse the two linked list to find M and N.
遍历两个链表以查找M和N。
Get back to the heads, then traverse |M − N| nodes on the longer list.
回到正面,然后遍历M−N | |节点在长名单上。
Now walk in lock step and compare the nodes until you found the common ones.
现在，在锁定步骤中，进行比较，直到找到常见的节点。

Edit: See http://richardhartersworld.com/cri/2008/linkedlist.html

编辑:参见http://richardhartersworld.com/cri/2008/linkedlist.html

#2

If possible, you could add a 'color' field or similar to the nodes. Iterate over one of the lists, coloring the nodes as you go. Then iterate over the second list. As soon as you reach a node that is already colored, you have found the intersection.

如果可能，您可以添加一个“颜色”字段或类似于节点。遍历其中的一个列表，并在执行过程中着色。然后迭代第二个列表。当您到达一个已经着色的节点时，您已经找到了交集。

#3

Dump the contents (or address) of both lists into one hash table. first collision is your intersection.

将两个列表的内容(或地址)转储到一个散列表中。第一次碰撞是你的交点。

#4

Check last nodes of each list, If there is an intersection their last node will be same.

检查每个列表的最后一个节点，如果有一个交集，它们的最后一个节点将是相同的。

#5

This is crazy solution I found while coding late at night, it is 2x slower than accepted answer but uses a nice arithmetic hack:

这是我在深夜编码时发现的一个疯狂的解决方案，它比被接受的答案慢了2倍，但使用了一个很好的算术方法:

public ListNode findIntersection(ListNode a, ListNode b) {
    if (a == null || b == null)
        return null;

    int A = a.count();
    int B = b.count();

    ListNode reversedB = b.reverse();

    // L = a elements + 1 c element + b elements
    int L = a.count();

    // restore b
    reversedB.reverse();

    // A = a + c
    // B = b + c
    // L = a + b + 1

    int cIndex = ((A+B) - (L-1)) / 2;
    return a.atIndex(A - cIndex);
}

We split lists at three parts: a this is part of the first list until start of the common part, b this is part of the second list until common part and c which is common part of two lists. We count list sizes then reverse list b, this will cause that when we start traversing list from a end we will end at reversedB (we will go a -> firstElementOfC -> reversedB). This will give us three equations that allow us to get length of common part c.

我们分三部分来划分列表:a这是第一个列表的一部分，直到common part开始，b这是第二个列表的一部分，直到common part和c，这是两个列表的常见部分。我们计算列表大小，然后反向列表b，这将导致当我们从一端开始遍历列表时，我们将在reversedB上结束(我们将go a -> firstElementOfC -> reversedB)。这将给我们三个方程，让我们得到公共部分c的长度。

This is too slow for programming competitions or use in production, but I think this approach is interesting.

这对于编程竞赛或在生产中使用来说太慢了，但是我认为这种方法很有趣。

#6

Maybe irrelevant at this point, but here's my dirty recursive approach. This takes O(M) time and O(M) space, where M >= N for list_M of length M and list_N of length N

也许这无关紧要，但这是我的脏递归方法。这需要O(M)时间和O(M)空间，其中M >= N，长度为M的list_M，长度为N。

Recursively iterate to the end of both lists, then count from the end for step 2. Note that list_N will hit null before list_M, for M > N
递归迭代到两个列表的末尾，然后从第2步的末尾开始计数。注意，list_N将在list_M之前达到null，对于M > N。
Same lengths M=N intersects when list_M != list_N && list_M.next == list_N.next
同样的长度M=N的交点，当list_M != list_N && & list_M。下一个= = list_N.next
Different lengths M>N intersects when list_N != null
不同长度的M>N相交于list_N != null。

Code Example:

代码示例:

Node yListsHelper(Node n1, Node n2, Node result) {
    if (n1 == null && n2 == null)
        return null;
    yLists(n1 == null ? n1 : n1.next, n2 == null ? n2 : n2.next, result);
    if (n1 != null && n2 != null) {
        if (n2.next == null) { // n1 > n2
            result.next = n1;
        } else if (n1.next == null) { // n1 < n2
            result.next = n2;
        } else if (n1 != n2 && n1.next == n2.next) { // n1 = n2
            result.next = n1.next; // or n2.next
        }
    }
    return result.next;
}

#1