Problem Statement:
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.
Examples:
- Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at ‘8’ - Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at ‘2’ - Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Constraints:
- The number of nodes in each list is in the range [0, 10⁴].
- -10⁵ ≤ Node.val ≤ 10⁵
- Lists are guaranteed to be acyclic and maintain their structure.
Approach:
- Store all nodes of
headBin aSet. - Traverse
headA; return the node when one exists in the set. - If no match is found, return
null.
Time and Space Complexity:
- Time Complexity: O(n + m), where n and m are lengths of listA and listB.
- Space Complexity: O(m), storing nodes of listB in a set.
var getIntersectionNode = function(headA, headB) {
let set = new Set();
while (headB) {
set.add(headB);
headB = headB.next;
}
while (headA) {
if (set.has(headA)) return headA;
headA = headA.next;
}
return null;
};
class Solution(object):
def getIntersectionNode(self, headA, headB):
visited = set()
while headB:
visited.add(headB)
headB = headB.next
while headA:
if headA in visited:
return headA
headA = headA.next
return None
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set visited = new HashSet<>();
while (headB != null) {
visited.add(headB);
headB = headB.next;
}
while (headA != null) {
if (visited.contains(headA)) return headA;
headA = headA.next;
}
return null;
}
}
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
unordered_set<ListNode*> visited;
while (headB) {
visited.insert(headB);
headB = headB->next;
}
while (headA) {
if (visited.count(headA)) return headA;
headA = headA->next;
}
return nullptr;
}
};
struct ListNode* getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
while (headA) {
struct ListNode *temp = headB;
while (temp) {
if (temp == headA) return headA;
temp = temp->next;
}
headA = headA->next;
}
return NULL;
}
public class Solution {
public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
HashSet<ListNode> visited = new HashSet<ListNode>();
while (headB != null) {
visited.Add(headB);
headB = headB.next;
}
while (headA != null) {
if (visited.Contains(headA)) return headA;
headA = headA.next;
}
return null;
}
}
