Dare2Solve
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
.
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.
pointerA
and pointerB
, to point to headA
and headB
respectively.pointerA
reaches the end of list A
, reset it to headB
.pointerB
reaches the end of list B
, reset it to headA
.pointerA
and pointerB
meet or both become null
.null
, there is no intersection, and the function should return null
.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.
O(1)
. The solution only uses a constant amount of extra space.
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;
}
};
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
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;
}
}
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;
};