查找两个链接列表的合并（相交）点☆☆☆☆

假设有两个不同长度的列表，它们合并在一个点上；我们如何知道合并点在哪里？

条件：

我们不知道长度

解：

可以说这违反了“仅分析每个列表一次”的条件，但是实现了乌龟和野兔算法（用于查找循环列表的合并点和循环长度），因此您从列表1开始，并且在到达列表NULL时您假装它是指向列表2开头的指针，从而创建了循环列表的外观。然后，该算法将告诉您确切的合并列表1有多远。

算法步骤：

制作一个如下的指针：
- 它每次都前进直到结束，然后
- 跳转到相反列表的开头，依此类推。
创建其中两个，指向两个头。
每次将每个指针前进1，直到它们在交点（IP）处相遇。一两次通过之后，就会发生这种情况。

要了解它，请计算从head1-> tail1 -> head2 -> intersection point和传播的节点数head2 -> tail2-> head1 -> intersection point。两者将相等（绘制链表的diff类型以进行验证）。原因是两个指针head1-> IP + head2->IP在IP再次到达之前必须经过相同的距离。因此，到它到达的时间IP，两个指针将相等，并且我们有了合并点。

实现方式：

CS

int FindMergeNode(Node headA, Node headB) {
    Node currentA = headA;
    Node currentB = headB;

    //Do till the two nodes are the same
    while(currentA != currentB){
        //If you reached the end of one list start at the beginning of the other one
        //currentA
        if(currentA.next == null){
            currentA = headB;
        }else{
            currentA = currentA.next;
        }
        //currentB
        if(currentB.next == null){
            currentB = headA;
        }else{
            currentB = currentB.next;
        }
    }
    return currentB.data;
}

java

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //boundary check
    if(headA == null || headB == null) return null;

    ListNode a = headA;
    ListNode b = headB;

    //if a & b have different len, then we will stop the loop after second iteration
    while( a != b){
        //for the end of first iteration, we just reset the pointer to the head of another linkedlist
        a = a == null? headB : a.next;
        b = b == null? headA : b.next;    
    }

    return a;
}

Y

# the idea is if you switch head, the possible difference between length would be countered. 
# On the second traversal, they either hit or miss. 
# if they meet, pa or pb would be the node we are looking for, 
# if they didn't meet, they will hit the end at the same iteration, pa == pb == None, return either one of them is the same,None

class Solution:
    # @param two ListNodes
    # @return the intersected ListNode
    def getIntersectionNode(self, headA, headB):
        if headA is None or headB is None:
            return None

        pa = headA # 2 pointers
        pb = headB

        while pa is not pb:
            # if either pointer hits the end, switch head and continue the second traversal, 
            # if not hit the end, just move on to next
            pa = headB if pa is None else pa.next
            pb = headA if pb is None else pb.next

        return pa # only 2 ways to get out of the loop, they meet or the both hit the end=None

常见问题FAQ