Intersection of Two Linked List

[kokocan12]

Problem

When two linked-list are given, find the initial node of intersection.
If there is no intersection, return null.

Approach

First, check they have intersection or not.
Then, save the move count of a, b.
Offset the diff of a, b, Then move each node one by one.

The code is below.

/**
 *        (4) -> 1                 a = 0
 *                 -> 8 -> 4 -> 5
 *   (5) -> 6 -> 1                 b = 0
 *  ----------------------------------------
 *        4 -> (1)                  a = 1
 *                 -> 8 -> 4 -> 5
 *   (5) -> 6 -> 1                  b = 0
 *  ----------------------------------------
 *          4 -> 1                  a = 2
 *                 -> (8) -> 4 -> 5
 *   (5) -> 6 -> 1                  b = 0
 *  ----------------------------------------
 *          4 -> 1                  a = 4
 *                 -> 8 -> 4 -> (5)
 *   (5) -> 6 -> 1                  b = 0
 *  ----------------------------------------
 *          4 -> 1                  a = 4
 *                 -> 8 -> 4 -> ((5))      If current node of a,b is same, they have intersection.
 *    5  -> 6 -> 1                  b = 5
 *  ----------------------------------------
 *   diff = b - a, pointer B move by diff at the beginning.
 *          (4) -> 1                
 *                 -> 8 -> 4 -> 5  Move one by one.
 *    5  -> (6) -> 1              
 *  ----------------------------------------
 *          4 -> (1)                
 *                 -> 8 -> 4 -> 5  Move one by one.
 *    5  -> 6 -> (1)
 *  ----------------------------------------
 *          4 -> 1                
 *                 -> ((8)) -> 4 -> 5  Same node detected. that is initial node of intersection.
 *    5  -> 6 -> 1
 */

const getIntersectionNode = function(headA, headB) {
    let a = 0;
    let b = 0;
    
    let currentA = headA;
    while(currentA && currentA.next) {
        a += 1;
        currentA = currentA.next;
    }
    
    let currentB = headB;
    while(currentB && currentB.next) {
        b += 1;
        currentB = currentB.next;
    }
    
    // Check they have intersection.
    if(currentA !== currentB) return null;
    
    
    let diff = Math.abs(a-b);
    
    // Move by diff at the beginning.
    currentA = headA;
    currentB = headB;
    if(a>b) {
        while(diff > 0) {
            currentA = currentA.next;
            diff -= 1;
        }
    } else {
        while(diff > 0) {
            currentB = currentB.next;
            diff -= 1;
        }
    }
    
    // Find initial node of intersection.
    while(currentA !== currentB) {
        currentA = currentA.next;
        currentB = currentB.next;
    }
    
    return currentA;
};