160. Intersection of Two Linked Lists.js

/**
Write a program to find the node at which the intersection of two singly linked lists begins.


For example, the following two linked lists:

A:          a1 → a2
                   
                    ↘

                     c1 → c2 → c3
                   
                    ↗
            
B:     b1 → b2 → b3
begin to intersect at node c1.


Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.
 */
/**
 * Algorithm: Two pointers
 * 1. I found most solutions here preprocess linkedlists to get the difference in len.
 *    Actually we don't care about the "value" of difference, we just want to make sure 
 *    two pointers reach the intersection node at the same time.
 *    We can use two iterations to do that. In the first iteration, we will reset the 
 *    pointer of one linkedlist to the head of another linkedlist after it reaches the 
 *    tail node. In the second iteration, we will move two pointers until they points 
 *    to the same node. Our operations in first iteration will help us counteract the 
 *    difference. So if two linkedlist intersects, the meeting point in second iteration 
 *    must be the intersection point. If the two linked lists have no intersection at all, 
 *    then the meeting pointer in second iteration must be the tail node of both lists, 
 *    which is null
 * 2. Notice that after 2 loops, a will go through List A and List B, b will go through 
 *    List B and List A. So eventually after 2 loops, a will have moved totally len(A + B) 
 *    steps, meanwhile, b will have moved totally len(B + A), therefore it's guaranteed that 
 *    a and b will meet at the end of the second loop, regardless of whether len(A) == len(B) 
 *    or not. So no flag is needed.
 * 3. In the case of List A and B having no interactions, a and b will meet at the end of the 
 *    second loop, when both a and b are equal to null
 */
/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
const getIntersectionNode = function(headA, headB) {
    if (headA === null || headB === null) {
        return null;
    }

    let a = headA;
    let b = headB;

    // if a & b have different len, then we will stop the loop after second iteration
    while (a !== b) {
    // for the end of first iteration, we just reset the pointer to the head of another linkedlist
        a = a === null ? headB : a.next;
        b = b === null ? headA : b.next;
    }

    return a;
}