Intersection of Two Linked Lists
Approach 1:
1) get length of both List
2) skip the extra nodes by moving pointer & decreasing length
3) now compare till u get common elemnt
var getIntersectionNode = function(headA, headB) {
let m = getLength(headA);
let n = getLength(headB);
let a = headA, b = headB;
while (m != n) {
if (m > n) {
m--;
a = a.next;
} else {
n--;
b = b.next;
}
}
while (a && a != b) {
a = a.next;
b = b.next;
}
return a;
}
const getLength = function(head) {
if (!head) {
return 0;
}
let length = 0;
let curr = head;
while (curr.next !== null) {
curr = curr.next;
length++;
}
return length;
}
Approach 2 :
1) two pointer
2) iterate in while till both are not same
3) if one is null return one & make other same as first
4) loop till mismatch
var getIntersectionNode = function(headA, headB) {
let ptrA = headA
let ptrB = headB
while(ptrA != ptrB){
if(ptrA == null){
ptrA = headB
}else{
ptrA = ptrA.next
}
if(ptrB == null){
ptrB = headA
}else{
ptrB = ptrB.next
}
}
return ptrA
};
Top comments (0)