
Description
Given the heads of two singly linked-lists headA
and headB
, the task is to find and return the node where the two lists intersect. If the two linked lists have no intersection at all, return null
.
Intuition
The key intuition behind this approach is that if two linked lists intersect, then the tail of the lists beyond the point of intersection must be the same. Therefore, the lists can be traversed in such a way that we align them starting from the intersection point.
By switching the heads of the two lists when reaching the end of one list, we can effectively equalize the lengths of the remaining parts of the lists. This ensures that the pointers will either meet at the intersection node or end up at null
if there is no intersection.
Approach
- Initialize two pointers,
pointerA
andpointerB
, to point toheadA
andheadB
respectively. - Traverse through both lists using the two pointers.
- If
pointerA
reaches the end of listA
, reset it toheadB
. - IfpointerB
reaches the end of listB
, reset it toheadA
. - Continue the traversal until
pointerA
andpointerB
meet or both becomenull
. - The meeting point, if any, is the intersection node. If they meet at
null
, there is no intersection, and the function should returnnull
.
Complexity
Time Complexity:
O(m + n)
where m
and n
are the lengths of the two linked lists. This is because in the worst case, both pointers traverse the entire length of both lists.
Space Complexity:
O(1)
. The solution only uses a constant amount of extra space.
Code
C++
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
ListNode *pointerA = headA;
ListNode *pointerB = headB;
while (pointerA != pointerB) {
pointerA = pointerA == nullptr ? headB : pointerA->next;
pointerB = pointerB == nullptr ? headA : pointerB->next;
}
return pointerA;
}
};
Python
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if not headA or not headB:
return None
pointerA = headA
pointerB = headB
while pointerA != pointerB:
pointerA = headB if pointerA is None else pointerA.next
pointerB = headA if pointerB is None else pointerB.next
return pointerA
Java
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode pointerA = headA;
ListNode pointerB = headB;
while (pointerA != pointerB) {
pointerA = (pointerA == null) ? headB : pointerA.next;
pointerB = (pointerB == null) ? headA : pointerB.next;
}
return pointerA;
}
}
JavaScript
var getIntersectionNode = function(headA, headB) {
if(headA===null || headB===null) {
return null;
}
let pointerA=headA;
let pointerB=headB;
while(pointerA!==pointerB) {
pointerA=pointerA===null?headA:pointerA.next;
pointerB=pointerB===null?headB:pointerB.next;
}
return pointerA;
};