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.
Intersection point means end of one linked list is linked with some node in another linked list and it forms a Y shape.
Input: Two Linked List
Output: Intersection Node or point, find Intersection Point in Two Linked List
This solution requires modifications to basic linked list data structure. Have a visited flag with each node. Traverse the first linked list and keep marking visited nodes. Now traverse second linked list, If you see a visited node again then there is an intersection point, return the intersecting node. This solution works in O(m+n)
⏰ Time complexity: O(m+n), with ’m’ and ’n’ representing the counts of nodes in the first and second lists, respectively. But this requires additional information with each node.
A variation of this solution that doesn’t require modification to basic data structure can be implemented using hash. Traverse the first linked list and store the addresses of visited nodes in a hash. Now traverse the second linked list and if you see an address that already exists in hash then return the intersecting node.
⏰ Time complexity: O(m+n), with ’m’ and ’n’ representing the counts of nodes in the first and second lists, respectively. But this requires additional information with each node.
🧺 Space complexity: O(m) as we store only first node
Method 4 - Use Length Difference of 2 Linked Lists 🥈#
While both lists may have different lengths, the combined length of list A and list B remains the same regardless of the order (list A + list B or list B + list A).
We don’t have to create modified list but instead we can simultaneously loop on A and B.
Start the loop on list A with pointer say a. Once listA is over, start with listB
Simultaneously, start the loop on list B with pointer say b. Once listB is over, start with listB
Continue with step 1 and 2, till we have a!=b. When, a==b, we break, because we are guaranteed that the last nodes of both iterations will be our blue nodes.
In that case, we would like for our loop will stop when we’ve reached the end of both combined lists. That is, when both our node pointers are null. Luckily, as you’ll see in the code, our while loop’s exist condition accounts for this edge case as well.
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA, b = headB;
while (a != b) { // loop until we found the first common node a = a ==null? headB : a.next; // once we're done with A, move to B b = b ==null? headA : b.next; // once we're done with B, move to A }
return a;
}
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA ==null|| headB ==null) returnnull;
// find last node of list A (c3) ListNode endA = headA;
while (endA.next!=null) {
endA = endA.next;
}
// join c3 to b1 making a c1...c3-b1...b3-c1 loop (if b3 indeed points to c1) endA.next= headB;
ListNode start =null; // if there's no cycle this will stay null// Floyd's cycle finder ListNode slow = headA, fast = headA;
while (fast !=null&& fast.next!=null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { // found a cycle// reset to beginning to find cycle start point (c1) start = headA;
while (slow != start) {
slow = slow.next;
start = start.next;
}
break;
}
}
// unjoin c3-b1 endA.next=null;
return start;
}