Description
Intersection of Two Linked Lists
Write a program to find the node at which the intersection of two singly linked lists begins.
请写一个程序，找到两个单链表最开始的交叉节点。
Notes:
- If the two linked lists have no intersection at all, return
null. - The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.
Examples
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
Answer
Using two pointers starting from headA and headB respectively to find the intersection if exists. If it does not exist, then both two pointers will reach its end and the last node of two linked lists will not be the same. If exists, then when each side of the pointer reaches its end, start from the other linked list and continue traversing until two pointers meet. The meeting point is the intersection of two lists since the sum of the length of the two lists is a determined value.
Time Complexity
O(n)
Code
C++
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(!headA || !headB) return nullptr;
ListNode *pa = headA, *pb = headB;
while(pa && pb)
{
if(pa == pb) return pa;
pa = pa->next;
pb = pb->next;
if(!pa && !pb) return nullptr;
if(!pa) pa = headB;
if(!pb) pb = headA;
}
return nullptr;
}
};
