从两个相交的链表中查找相交节点
假设有两个单链表，它们在某个点相交并成为单个链表。
两个列表的头部或起始指针都是已知的，但交叉节点是未知的。 此外，列表中每个列表中的节点数量在它们相交之前是未知的，并且两个列表可能具有不同，即List1在到达交叉点之前可能有n个节点，而List2可能在到达交点之前有m个节点，其中m和n可能是
- m = n，
- m <n或
- m> n
一种已知或简单的解决方案是将第一列表中的每个节点指针与第二列表中的每个其他节点指针进行比较，匹配节点指针将通过该指针引导我们到交叉节点。 但是，在这种情况下，时间复杂度将是O（n 2 ），这将是很高的。
找到交叉节点的最有效方法是什么？
这需要O（M + N）时间和O（1）空间，其中M和N是链表的总长度。 如果公共部分很长（即M，N >> m，n）可能效率低下
- 遍历两个链表以找到M和N.
- 回到头部，然后遍历| M – N | 较长列表上的节点。
- 现在进入锁定步骤并比较节点，直到找到常见节点。
编辑：请参阅http://richardhartersworld.com/cri/2008/linkedlist.html
如果可能，您可以添加“颜色”字段或类似于节点。 迭代其中一个列表，随时为节点着色。 然后迭代第二个列表。 一旦到达已经着色的节点，就会找到交叉点。
将两个列表的内容（或地址）转储到一个哈希表中。 第一次碰撞是你的交集。
检查每个列表的最后一个节点，如果有一个交叉点，它们的最后一个节点将是相同的。
这是我在深夜编码时发现的疯狂解决方案，它比接受的答案慢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); } 我们将列表拆分为三个部分： a这是第一个列表的一部分直到公共部分的开始， b这是第二个列表的一部分，直到公共部分和c是两个列表的公共部分。 我们计算列表大小然后反转列表b ，这将导致当我们从一端开始遍历列表时，我们将以a -> firstElementOfC -> reversedB结束（我们将去a -> firstElementOfC -> reversedB ）。 这将给我们三个方程，允许我们得到公共部分c长度。
这对于编程比赛或在制作中使用来说太慢了，但我认为这种方法很有趣。
也许在这一点上无关紧要，但这是我的脏递归方法。 这需要O(M)时间和O(M)空间，其中M >= N ，长度为M list_N ，长度为N list_N
- 递归迭代到两个列表的末尾，然后从步骤
2开始计数。 请注意，list_N将在list_M之前命中null，因为M > N - 当
list_M != list_N && list_M.next == list_N.next时，相同的长度M=N相交 - 当
list_N != null时，不同的长度M>N相交
代码示例：
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; }