[tabby title=”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
[tabby title=”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) );
[tabbyending]
