Find the intersection point of two linked list

Learn how to find the intersection point of two linked list.

Example

Input:
13 -> 4 -> 12 -> 27 -> null
14 -> 4 -> 82 -> 11 -> 12 -> 27 -> null

Output:
12

An intersection point is an element present in both the linked list such that there is equal amount of elements after them.

Naive approach

One simple approach is to iterate all the elements of first list and then check if it is present in the second list or not. It will take O(m * n) time.

Using set

Another approach is to use a hashset and store the all the elements of the first list in it and then check in the second list if any of the element is there in the hashset or not. This is an optimized way which will run in O(m + n) but it will require O(m) or O(n) space depending upon which is less.

Efficient approach to find the intersection point of two linked list.

This approach basically removes the need of using extra space.

Implementation

• Get the size of both the linked lists.
• Calculate the difference in the size of both the list. d = |l1 – l2|
• Move the pointer of the longer list d steps forward.
• Iterate both the list simultaneously and check if any element matches or not. If matches then return it else return null.

const intersect = (head1, head2, size1, size2) => {
    //Temp list
    let list1node = null;;
    let list1length = size1;
    let list2node = null;;
    let list2length = size2
    
    //Get the diference and change the order
    let length_difference = 0;
    if (list1length >= list2length) {
        length_difference = list1length - list2length;
        list1node = head1;
        list2node = head2;
    } else {
        length_difference = list2length - list1length;
        list1node = head2;
        list2node = head1;
    }
    
    //Move the longest list d steps forward
    while (length_difference > 0) {
        list1node = list1node.next;
        length_difference--;
    }
    
    //Check for common element in both list or intersection point
    while (list1node && list2node) {
        if (list1node.element === list2node.element) {
            return list1node.element;
        }
        list1node = list1node.next;
        list2node = list2node.next;
    }

    return null;
};

Input:
const ll1 = new linkedlist();
const ll2 = new linkedlist();

ll1.append(13);
ll1.append(4);
ll1.append(12);
ll1.append(27);

ll2.append(14);
ll2.append(4);
ll2.append(82);
ll2.append(11);
ll2.append(12);
ll2.append(27);

console.log(intersect(ll1.getHead(), ll2.getHead(), ll1.size(), ll2.size()));

Output:
12

Time complexity: O(m + n).
Space complexity: O(1).