Hashim
December 16, 2016
2:47 am
Programming

Algorithm {Intersection of Two Linked Lists}

Today I will describe about easy but with interesting solution problem – Intersection of Two Linked Lists. OK, let’s read problem description:

Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists:
A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
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.

So, what can we see? We have two linked lists where last part can be the same, like in the pic above. OK, try to think how to find first element of the common part.

First solution can be based on two loops. Run two loops for each element of list1 check all elements of list2, yes, complexity will be bad and equals to O(nm) if n ==m , O(n^2), but we do not use additional memory.

Second one can be based on recursion. Main idea run through 2 lists to the end and in back way compare each element. If elements are not equal return next one. Complexity will be O(n+m) ~ O(n), but memory usage will be O(n+m) which is not good. Code example:

public class Intersection {
ListNode result = null;
 
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null && headB == null) {
return null;
}
if (headA != null && headB != null) {
lookUp(headA, headB);
return result;
}
return null;
}
 
private void lookUp(ListNode headA, ListNode headB) {
if (headA.next == null && headB.next == null) {
return;
}
lookUp(headA.next == null ? headA : headA.next, headB.next == null ? headB : headB.next);
 
if (!headA.equals(headB)) {
if (result == null)
result = headA.next;
}
}
}

Third one solution can be based on the set. Run through list1, store all elements in set and after that run through list2 check if element is present it’s intersection return it if no, return null. Complexity will be O(n+m) ~ O(n), but memory usage will be O(n+m) which is not good (can be O(n) or O(m)). Code example:

public class Intersection {
 
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null && headB == null) {
return null;
}
ListNode node = headA;
 
Set<ListNode> nodeSet = new HashSet<ListNode>();
 
while (node!=null){
nodeSet.add(node);
node = node.next;
}
 
node = headB;
 
while (node!=null){
if(!nodeSet.add(node)) // can be changed to contains
return node;
node = node.next;
}
return null;

}

OK, all solutions are not good, so, we can use a trick:

Counts lengths of both lists.
Counts difference between them.
Run through bigger list to different length, for align both lists
Run through both lists and compare elements.

Hmm, perfect lest implement it:

/**
* 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 aCount = count(headA);
int bCount = count(headB);
int diff = aCount - bCount;
if (diff < 0)
diff = diff * -1;
 
if (aCount > bCount) {
while (diff > 0 && headA != null) {
headA = headA.next;
diff--;
}
} else if (bCount > aCount) {
while (diff > 0 && headB != null) {
headB = headB.next;
diff--;
}
}
 
if (diff > 0){
return null;
}
 
while (headA != null && headB != null) {
if(headA.equals(headB))
return headA;
headA = headA.next;
headB = headB.next;
}
return null;
}
private int count(ListNode head) {
int count = 0;
ListNode node = head;
while (node != null) {
count++;
node = node.next;
}
return count;
}

}

So, leetcode accepted that solution, that is good, complexity as written in task description O(n) and memory O(1). Perfect! Thanks.