LeetCode: Intersection of Two Linked Lists — Optimal Solution Deeply Explained

Intersection of Two Linked Lists Optimal Solution Deeply Explained

Table of Content

• Introduction
• Intuition/Solution
• Step-by-Step Visual Guide
• Implementation Code

Introduction

Discovering the intersection point of two linked lists can be a challenging task, but by using the right approach, it becomes efficient and elegant.

We will explore the two-pointer technique, an intuitive method to find the intersection of two linked lists with a time complexity of O(n+m) and space complexity of O(1).

We will guide you step by step, using clear visuals to demonstrate how the algorithm works, ensuring a thorough understanding of this powerful technique.

Intuition/Solution

Given a list A and list B shown here

List A: 1 -> 3 -> 5 -> 7 -> 9
                             \
                              11 -> 13 -> 15
                             /
List B:       2 -> 4 ------>

• List A has length of 8, which is [1, 3, 5, 7, 9, 11, 13, 15]
• List B has a length of 5, which is [2, 4, 11, 13, 15]

Keep in mind that the length of list A+B will equal to the length of list B+A, as you can see here

List A+B: 1 -> 3 -> 5 -> 7 -> 9 -> 11 -> 13 -> 15 -> 2 -> 4 -> 11 -> 13 -> 15

List B+A: 2 -> 4 -> 11 -> 13 -> 15 -> 1 -> 3 -> 5 -> 7 -> 9 -> 11 -> 13 -> 15

• List A+B has length of 13, which is [1, 3, 5, 7, 9, 11, 13, 15, 2, 4, 11, 13, 15]
• List B+A has length of 13, which is [2, 4, 11, 13, 15, 1, 3, 5, 7, 9, 11, 13, 15]

The idea is to have two pointers, one for each linked list (list A+B and list B+A), traversing the lists from their heads. If both pointers reach the end of their respective lists without finding an intersection, there is no intersection. If an intersection is found, the traversal will stop, and the intersecting node will be returned.

1. Initialize two pointers, p1 and p2, pointing to the heads of the linked lists headA and headB, respectively.
2. Traverse the linked lists using these pointers. Move p1 and p2 to the next node in each iteration.
3. If p1 reaches the end of the list, reset it to the head of the other list (headB). Similarly, if p2 reaches the end, reset it to the head of the other list (headA).
4. If p1 and p2 meet at some point (i.e., p1 == p2), that's the intersection node. Return this node.
5. If both pointers reach the end of their respective lists without finding an intersection, there is no intersection. Return null.

Step-by-Step Visual Guide

Case 1 :

When the lists are intersecting

List A: 1 -> 3 -> 5 -> 7 -> 9
                             \
                              11 -> 13 -> 15
                             /
List B:       2 -> 4 ------>

Step 1:
Initialize two pointers, p1 and p2, to the heads of List A and List B.

List A: [1]-> 3 -> 5 -> 7 -> 9 -> 11 -> 13 -> 15
         p1

List B: [2]-> 4 -> 11 -> 13 -> 15
         p2

Step 2:
Move both pointers one step forward.

List A: 1 ->[3]-> 5 -> 7 -> 9 -> 11 -> 13 -> 15
             p1

List B: 2 ->[4]-> 11 -> 13 -> 15
             p2

Step 3: Continue moving pointers forward. When p1 reaches the end of List A, move it to the head of List B. When p2 reaches the end of List B, move it to the head of List A.

List A: 1 -> 3 -> 5 -> 7 -> 9 ->[11]-> 13 -> 15
                                 p2

List B: [2]-> 4 -> 11 -> 13 -> 15
         p1

Step 4:
Keep moving the pointers. They will eventually meet at the intersection point. Both pointers are at the intersection point (Node 11). Return the intersection node.

List A: 1 -> 3 -> 5 -> 7 -> 9 ->[11]-> 13 -> 15
                                 p1
                                   
List B: 2 -> 4 ->[11]-> 13 -> 15
                  p2

Case 2:

When the lists are NOT intersecting

List A: 1 -> 3 -> 5 -> 7 -> 9

List B: 2 -> 4 -> 6 -> 8 -> 10

Step 1:
Initialize two pointers, p1 and p2, to the heads of List A and List B.

List A: [1]-> 3 -> 5 -> 7 -> 9
         p1

List B: [2]-> 4 -> 6 -> 8 -> 10
         p2

Step 2:
Move both pointers one step forward.

List A: 1 ->[3]-> 5 -> 7 -> 9
             p1

List B: 2 ->[4]-> 6 -> 8 -> 10
             p2

Step 3:
Continue moving pointers forward. When p1 reaches the end of List A, move it to the head of List B. When p2 reaches the end of List B, move it to the head of List A.

List A: 1 -> 3 -> 5 -> 7 -> [9]
                            p2

List B: 2 -> 4 -> 6 -> 8 -> [10]
                             p1

Step 4:
Keep moving the pointers. They will eventually reach the end of their respective lists.

List A: [1] -> 3 -> 5 -> 7 -> 9
         p2

List B: [2] -> 4 -> 6 -> 8 -> 10
         p1

Step 5:
Both pointers have now reached the end of their respective lists again without meeting. This confirms that there’s no intersection between the two lists. The algorithm returns null.

List A: 1 -> 3 -> 5 -> 7 -> [9]
                             p2

List B: 2 -> 4 -> 6 -> 8 -> [10]
                             p1

Implementation Code

Python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    p1, p2 = headA, headB
    
    while p1 != p2:
        p1 = p1.next if p1 else headB
        p2 = p2.next if p2 else headA

    return p1

Javascript

// Definition for singly-linked list.
function ListNode(val) {
    this.val = val;
    this.next = null;
}

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    let p1 = headA;
    let p2 = headB;

    while (p1 !== p2) {
        p1 = p1 === null ? headB : p1.next;
        p2 = p2 === null ? headA : p2.next;
    }

    return p1;
};