Intersection of Two Linked Lists

One common problem involving linked lists is determining if and where two lists intersect. The intersection point is defined as the node at which the two linked lists share common elements. This problem poses an interesting challenge due to the varying lengths of the lists and the need to efficiently identify the intersection point.

In this article, we will explore different approaches to solve the intersection point problem, implement them in javascript and discuss their respective time and space complexities.

Problem Statement:

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

---

Approach 1: Brute Force

One simple approach is to compare each node of the first linked list with each node of the second linked list. If a node in the first linked list matches with any node in the second linked list, that is the intersection point.

1. The function will take two linked lists as input.

2. Use two nested loops to compare the node values at each iteration in both the linked lists.

3. If the intersection is found then return that node. Otherwise, return null.

// ES6 Arrow Function
const getIntersectionNode = (headA, headB) => {
    let ha = headA;

    while(ha !== null) {
        let hb = headB;
        while(hb !== null) {
            if(ha === hb) return ha;
            hb = hb.next;
        }
        ha = ha.next;
    }

    // No intersection found
    return null;
}

Time Complexity: O(N * M)

We iterate through the first linked list of length N and, for each node, we iterate through the second linked list of length M. The worst-case scenario occurs when there is no intersection, and we need to compare every node of the first linked list with every node of the second linked list.

Space Complexity: O(1)

This approach uses constant space since we do not require any additional data structures to solve the problem.

---

Approach 2: Hash Set

1. In this approach, we can use a hash set to store the memory addresses of the nodes in the first linked list.

2. Then, we traverse the second linked list and check if any node’s memory address exists in the hash set.

3. If we find a match, that is the intersection point. Otherwise, return null.

// ES6 Arrow Function
const getIntersectionNode = (headA, headB) => {
    let set = new Set();

    let ha = headA;
    while(ha !== null) {
        set.add(ha);
        ha = ha.next;
    }

    let hb = headB;
    while(hb !== null) {
        if(set.has(hb)) return hb;
        hb = hb.next;
    }

    return null;
}

Time Complexity: O(N + M)

We iterate through the first linked list of length N to store its nodes’ memory addresses in the hash set. Then, we iterate through the second linked list of length M to check if any node’s memory address exists in the hash set. Both iterations are linear. Therefore the time complexity is linear.

Space Complexity: O(N)

In the worst case, all nodes of the first linked list will be stored in the hash set. Therefore, the space complexity is proportional to the length of the first linked list.

---

Approach 3: Two Pointers

1. First, we find the lengths of both linked lists.

2. Then, we move the pointer of the longer linked list ahead by the difference in lengths. This adjustment ensures that both pointers are starting at the same relative position from the intersection point.

3. After adjusting the pointers, we iterate through both linked lists simultaneously by advancing the pointers one node at a time.

4. During each iteration, we compare the nodes pointed by the two pointers.

5. If we find a matching node, that is the intersection point.

6. If we reach the end of both linked lists without finding an intersection, there is no intersection, and we return null.

// ES6 Arrow Function
const getIntersectionNode = (headA, headB) => {
    let ha = headA, hb = headB;

    // Find the length of both linked lists
    let lenA = getLength(ha);
    let lenB = getLength(hb);

    // Adjust the pointer to make them start at the same relative position from the intersection point
    while(lenA > lenB) {
        ha = ha.next;
        lenA--;
    }

    while(lenB > lenA) {
        hb = hb.next;
        lenB--;
    }

    // Traverse both the linked lists simultaneously util the intersection point is found
    while(ha !== hb) {
        ha = ha.next;
        hb = hb.next;
    }

    // Intersection node or null (if no intersection is found)
    return ha;
}

const getLength = node => {
    let len = 0; 
    while(node !== null) {
        len++;
        node = node.next;
    }
    return len;
}

Time Complexity: O(N + M)

We first find the lengths of both linked lists, which takes O(N + M) time as we need to traverse each list once. Then, the adjustment of pointers to make them start at the same relative position takes constant time. Finally, the iteration through both linked lists simultaneously takes O(N + M) time in the worst case, as we traverse until we find the intersection point or reach the end of both lists.

Space Complexity: O(1)

Regardless of the size of the linked lists, the space complexity remains constant.

---

And there you have it guys! We’ve explored different approaches, optimized our solutions, and hopefully had some fun along the way. I hope this article has provided you with valuable insights and helped you better understand the different approaches to solving this problem. Happy coding!

Problem - Leetcode 160