160-相交链表

LeetCode

发布日期: 2021-06-07

LeetCode 160. Intersection of Two Linked Lists

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

It is guaranteed that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

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

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'

method: 指针交叉遍历

一个链表的指针遍历完了，就换到另一条链表继续遍历，两个指针相遇说明有相交，没相遇最后会都等于nullptr返回

情况一：两个链表相交

链表 headA 和 headB 的长度分别是 m 和 n

如果 a = b，则两个指针会同时到达两个链表相交的节点；
如果 a != b，在指针 pA 移动了 a+c+b 次、指针 pB 移动了 b+c+a 次之后，两个指针会同时到达两个链表相交的节点，该节点也是两个指针第一次同时指向的节点。

情况二：两个链表不相交

如果 m = n，则两个指针会同时到达两个链表的尾节点，然后同时变成空值 null，此时返回 null；
如果 m != n，则由于两个链表没有公共节点，两个指针也不会同时到达两个链表的尾节点，因此两个指针都会遍历完两个链表，在指针 pA 移动了 m+n 次、指针 pB 移动了 n+m 次之后，两个指针会同时变成空值 null，此时返回 null。

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *pA = headA;
    ListNode *pB = headB;
    while (pA != pB) {
        if (pA) pA = pA->next;
        else pA = headB;
        if (pB) pB = pB->next;
        else pB = headA;
    }
    return pA;
}