DEV Community

ZeeshanAli-0704
ZeeshanAli-0704

Posted on

Intersection of Two Linked Lists

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;
}

Enter fullscreen mode Exit fullscreen mode

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
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)