LeetCode Algorithm 160. 相交链表

160. 相交链表

Ideas

这题之前左神算法课的时候也讲过，那是一个带环的相交链表，不过原理都是一样的。

双指针，a指针先沿着headA开始走，走到头之后开始沿着headB继续走，b指针先沿着headB开始走，走到头之后开始沿着headA继续走。

假设链表headA和headB的长度分别是m和n，链表headA的不相交部分有a个节点，链表headB的不相交部分有b个节点，两个链表相交的部分有c个节点，则有 a+c=m，b+c=n。

a指针走了a+c+b次，b指针走了b+c+a次之后，两个指针就会同时到达两个链表相交的结点。

Code C++

class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (headA == nullptr || headB == nullptr) { return nullptr; } ListNode *a = headA, *b = headB; while (a != b) { a = a == nullptr ? headB : a->next; b = b == nullptr ? headA : b->next; } return a; } };