Table of Contents
Task
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.
Example 1:
This problem was taken from Leetcode
Solution
We are not asked to compare the values inside the linked lists but the list node objects, so we could ignore the values of the list.
Approach 1: Brute Force
For each node ai in list A, traverse the entire list B and check if any node in list B coincides with ai.
Complexity Analysis
- Time complexity : O(mn).
- Space complexity : O(1).
Approach 2: Calculating the length of the two linked lists and compare the elements that could potentially intersect.
- Time complexity : O(m+n).
- Space complexity : O(m) or O(n).
function ListNode(val) {
this.val = val;
this.next = null;
}
headA = new ListNode(4);
headA.next = new ListNode(1);
headB = new ListNode(5);
headB.next = new ListNode(0);
headB.next.next = new ListNode(1);
headA.next.next = headB.next.next.next = new ListNode(8);
headB.next.next.next.next = headA.next.next.next = new ListNode(4);
headB.next.next.next.next.next = headA.next.next.next.next = new ListNode(5);
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
let node = headA;
let countA = 0;
while(node != null ) {
node = node.next;
countA ++;
}
node = headB;
let countB = 0;
while(node != null ) {
node = node.next;
countB ++;
}
let longList, shortList, diff, iteratorLongLength,iteratorShortLength;
if(countA > countB)
longList = headA, shortList = headB, diff = countA - countB;
else
longList = headB, shortList = headA, diff = countB - countA;
let i = 0;
while(shortList != null) {
if(i < diff ) {
longList = longList.next;
}
else {
console.log("long list, short list", longList.val, shortList.val);
if(longList == shortList)
return longList.val;
longList = longList.next;
shortList = shortList.next;
}
i ++;
}
};
console.log (getIntersectionNode(headA, headB) );
what we just did:
– we calculated the length of the first list to be 5 and the second 6 (first and the second loop)
– the third loop is doing two things:
– first since the difference between the shorter and the longer list is 1 we move the cursor to the second element of the longer list (lines 59-61)
– after we position the longer list cursor at the second element we could start comparing (line 64)
If we execute the function we will see this result:
long list, short list 0 4
long list, short list 1 1
long list, short list 8 8
And the third element is exactly where the intersection is.
Approach 3: Traverse both lists and when reaching the end of each one, move the pointer to the opposite list and traverse again till intersection is found.
- Time complexity : O(m+n).
- Space complexity : O(m) or O(n).
This basically is the same concept as in the example above, just written in a bit more elegant way.
function ListNode(val) {
this.val = val;
this.next = null;
}
headA = new ListNode(4);
headA.next = new ListNode(1);
headB = new ListNode(5);
headB.next = new ListNode(0);
headB.next.next = new ListNode(1);
headA.next.next = headB.next.next.next = new ListNode(8);
headB.next.next.next.next = headA.next.next.next = new ListNode(4);
headB.next.next.next.next.next = headA.next.next.next.next = new ListNode(5);
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
let nodeA = headA;
let nodeB = headB;
let swapA = false;
let swapB = false;
var i = 0;
while(nodeA != null && nodeB!=null ) {
// node A
if(!swapA && nodeA.next == null) {
nodeA = headB;
swapA = true;
}
else {
nodeA = nodeA.next;
}
// node B
if(!swapB && nodeB.next == null) {
nodeB = headA;
swapB = true;
}
else {
nodeB = nodeB.next;
}
if(nodeA === nodeB)
return nodeA.val;
}
};
console.log (getIntersectionNode(headA, headB) );
what we just did:
– traverse listA and listB till we reach the end of each one (lines 47 and 55) .
– once we reach the end of each list we point the cursor to the opposite list (lines 43 and 51)
Approach 4: Hash Table
Traverse list A and store the address / reference to each node in a hash set. Then check every node bi in list B: if bi appears in the hash set, then bi is the intersection node.
Complexity Analysis
- Time complexity : O(m+n).
- Space complexity : O(m) or O(n).
function ListNode(val) {
this.val = val;
this.next = null;
}
// link-list A: [4,1,8,4,5]
// link-list B: [5,0,1,8,4,5]
headA = new ListNode(4);
headA.next = new ListNode(1);
headB = new ListNode(5);
headB.next = new ListNode(0);
headB.next.next = new ListNode(1);
headA.next.next = headB.next.next.next = new ListNode(8);
headB.next.next.next.next = headA.next.next.next = new ListNode(4);
headB.next.next.next.next.next = headA.next.next.next.next = new ListNode(5);
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
let hashMap = {};
let node = headA;
while(node != null ) {
hashMap[node.val] = node;
node = node.next;
}
node = headB;
while(node != null) {
let val = node.val;
if(hashMap[val] == node) {
return val;
}
node = node.next;
}
};
console.log ("result: ", getIntersectionNode(headA, headB) );