Intersection in a linked List
Problem Statement
Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists, begin to intersect at node c1.
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.
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
Approach
If the intersection point exists and both linked lists are of same size then its easy to find node. But when the sizes are different, then we know the number of nodes after the intersection point in both lists are same.Therefore, the number of nodes would only differ before the intersection point. If we move d(difference in length of 2 lists) nodes in the longer list first and then start moving through both lists, then the size of both would be same from this point.
Find the length of both linked lists and check which of the below conditions meet:
- Size of both linked lists is same.
- If this is the case, start from the head of both the linked lists. Move one node at time and keep checking if the nodes are same. If yes, then we found the intersecting node else if we reach null then there is no intersecting node.
- One of the linked list is greater than the other one.
- In this case, calculate the difference (d) between the lengths of 2 linked lists.
- Traverse through the longer linked list first and move d nodes. After reaching the dth node, start traversing the short linked list and long linked list in parallel. Check each node from both the linked lists for equality. Return the intersecting node if found else return null.
Run Time
The run time complexity of this code is O(n)
Java Code
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
int lengthA = getLength(headA);
int lengthB = getLength(headB);
int difference = lengthA - lengthB;
if(difference == 0){
ListNode currentA = headA;
ListNode currentB = headB;
while(currentA != null || currentB != null){
if(currentA == currentB){return currentA;}
currentA = currentA.next;
currentB = currentB.next;
} return null;}
else if(difference > 0){
return getPoint(difference,headA,headB);
}
else{
return getPoint(Math.abs(difference),headB,headA);
}
}
/* Calculate and return the length of the linked list*/
private int getLength(ListNode head){
ListNode current = head;
int length = 0;
while(current != null){
length++;
current = current.next;
}return length;
}
/*
Find and return the intersection node when length of two linked lists are different.
*/
private ListNode getPoint(int diff, ListNode headLong, ListNode headShort){
ListNode currentLong = headLong;
while(diff != 0){
diff--;
currentLong = currentLong.next;
}
ListNode currentShort = headShort;
while(currentLong != null || currentShort != null){
if(currentLong == currentShort){
return currentLong;
}
currentLong = currentLong.next;
currentShort = currentShort.next;
} return null;
}
}