Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Intersection of Two Linked Lists

EASYProblemSolveExternal Links

Description

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 do not intersect at all, return null.

Two linked lists intersect when they share the same physical node from some point onward. This means after the intersection node, both lists follow the exact same chain of nodes until the end. The intersection is determined by reference (the same node object in memory), not merely by value.

The linked lists must retain their original structure after the function returns — do not modify them.

Examples

Example 1

Input: listA = [4, 1, 8, 4, 5], listB = [5, 6, 1, 8, 4, 5], intersection at node with value 8

Output: Node with value 8

Explanation: List A follows 4 → 1 → 8 → 4 → 5, and list B follows 5 → 6 → 1 → 8 → 4 → 5. Starting from the node with value 8, both lists share the same physical nodes (8 → 4 → 5). So the intersection node is the one with value 8. Note that although list B also has a node with value 1, it is a different node object from the node with value 1 in list A.

Example 2

Input: listA = [1, 9, 1, 2, 4], listB = [3, 2, 4], intersection at node with value 2

Output: Node with value 2

Explanation: List A: 1 → 9 → 1 → 2 → 4. List B: 3 → 2 → 4. From the node with value 2 onward, both lists share the same nodes (2 → 4). The intersection is at the node with value 2.

Example 3

Input: listA = [2, 6, 4], listB = [1, 5], no intersection

Output: null

Explanation: List A: 2 → 6 → 4. List B: 1 → 5. These two lists do not share any common nodes — their tails are different. So there is no intersection, and we return null.

Constraints

  • The number of nodes of listA is m
  • The number of nodes of listB is n
  • 1 ≤ m, n ≤ 3 × 10^4
  • 1 ≤ Node.val ≤ 10^5
  • 0 ≤ skipA ≤ m
  • 0 ≤ skipB ≤ n
  • intersectVal is 0 if listA and listB do not intersect
  • There are no cycles anywhere in the linked structure

Editorial

Brute Force

Intuition

The most straightforward way to find the intersection is to check every single node of one list against every node of the other list. For each node in list A, we walk through the entire list B and check if any node in B is the exact same node (same memory reference) as the current node in A.

Think of two groups of people standing in separate lines who may or may not merge into a single line at some point. To find where they merge, you could take the first person from line A and walk along line B checking if they are the same person. Then repeat with the second person from line A, and so on. The first person you find who appears in both lines marks the merging point.

Step-by-Step Explanation

Let's trace through with listA = [4, 1, 8, 4, 5] and listB = [5, 6, 1, 8, 4, 5], where they intersect at the node with value 8 (node index 2 in A, index 3 in B).

Step 1: Start with nodeA = first node of A (val=4).

Step 2: Walk through all of list B: compare nodeA (val=4) with each node in B.

  • nodeA (4) vs nodeB (5): different nodes → no match
  • nodeA (4) vs nodeB (6): different nodes → no match
  • nodeA (4) vs nodeB (1): different nodes → no match
  • nodeA (4) vs nodeB (8): different nodes → no match
  • nodeA (4) vs nodeB (4): these have the same VALUE but are DIFFERENT nodes in memory → no match
  • nodeA (4) vs nodeB (5): different → no match
  • Exhausted list B with no match. Move to next node in A.

Step 3: nodeA = second node of A (val=1).

  • Walk through B again: 5, 6, 1, 8, 4, 5 — none is the same NODE as A's second node.
  • No match found.

Step 4: nodeA = third node of A (val=8). This is the actual intersection node.

  • nodeA (8) vs nodeB (5): different → no
  • nodeA (8) vs nodeB (6): different → no
  • nodeA (8) vs nodeB (1): different → no
  • nodeA (8) vs nodeB (8): SAME NODE! These are the same physical node in memory.

Step 5: Return nodeA — the node with value 8 is the intersection point.

Brute Force — Check Every Node Pair — Watch how we fix each node from list A and scan through all of list B to find a matching node reference. This exhaustive search finds the intersection but is slow.

Algorithm

  1. For each node nodeA in list A:
    • For each node nodeB in list B:
      • If nodeA and nodeB are the same node (same reference), return nodeA.
  2. If no common node is found after checking all pairs, return null.

Code

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* currA = headA;
        while (currA != nullptr) {
            ListNode* currB = headB;
            while (currB != nullptr) {
                if (currA == currB) {
                    return currA;
                }
                currB = currB->next;
            }
            currA = currA->next;
        }
        return nullptr;
    }
};
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        currA = headA
        while currA:
            currB = headB
            while currB:
                if currA is currB:
                    return currA
                currB = currB.next
            currA = currA.next
        return None
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode currA = headA;
        while (currA != null) {
            ListNode currB = headB;
            while (currB != null) {
                if (currA == currB) {
                    return currA;
                }
                currB = currB.next;
            }
            currA = currA.next;
        }
        return null;
    }
}

Complexity Analysis

Time Complexity: O(m × n)

For each of the m nodes in list A, we potentially scan all n nodes in list B. This gives us m × n comparisons in the worst case. With m and n up to 3 × 10^4, this could mean up to ~9 × 10^8 comparisons.

Space Complexity: O(1)

We only use two pointer variables. No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force approach has O(m × n) time complexity. With m and n both up to 30,000, this means up to 900 million comparisons — far too slow for typical time limits.

The core inefficiency is that for every single node in A, we re-scan the entire list B from scratch. We do not remember any information from previous scans. If we could store the nodes of one list in a data structure that supports O(1) lookup, we could reduce the inner loop from O(n) to O(1), bringing total time to O(m + n).

Better Approach - Hash Set

Intuition

Instead of scanning list B repeatedly, we can store all nodes of list A in a hash set first. Then we walk through list B once, checking for each node whether it exists in the set. The first node from B found in the set is the intersection point.

Imagine registering all guests at a party (list A) in a guest book. Then as people from a second event (list B) walk in, you check each person against the guest book. The first person who already appears in the book is where the two events overlap.

Using a hash set gives us O(1) average lookup time per node, reducing total time from O(m × n) to O(m + n).

Step-by-Step Explanation

Let's trace with listA = [4, 1, 8, 4, 5] and listB = [5, 6, 1, 8, 4, 5], intersecting at node with value 8.

Step 1: Initialize an empty hash set.

Step 2: Traverse list A and store each node reference in the set.

  • Insert node(4, index 0) → set = {node0}
  • Insert node(1, index 1) → set = {node0, node1}
  • Insert node(8, index 2) → set = {node0, node1, node2}
  • Insert node(4, index 3) → set = {node0, node1, node2, node3}
  • Insert node(5, index 4) → set = {node0, node1, node2, node3, node4}

Step 3: Traverse list B and check each node against the set.

  • nodeB = node(5, B-index 0): is it in set? No (this is B's own node, not shared with A)

Step 4: Move to next B node.

  • nodeB = node(6, B-index 1): is it in set? No

Step 5: Move to next B node.

  • nodeB = node(1, B-index 2): is it in set? No (B's node with value 1 is a different object from A's node with value 1)

Step 6: Move to next B node.

  • nodeB = node(8, index 2): is it in set? YES! This is the same node object as A's node at index 2.

Step 7: Return node(8) — the intersection point.

Hash Set — Store List A, Then Scan List B — Watch how we insert all nodes from list A into a hash set, then probe the set for each node in list B. The first hit reveals the intersection.

Algorithm

  1. Create an empty hash set.
  2. Traverse list A from head to end, inserting each node reference into the set.
  3. Traverse list B from head to end:
    • For each node, check if it exists in the set.
    • If found, return that node — it is the intersection.
  4. If no node from B is found in the set, return null.

Code

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> visited;
        ListNode* currA = headA;
        while (currA != nullptr) {
            visited.insert(currA);
            currA = currA->next;
        }
        ListNode* currB = headB;
        while (currB != nullptr) {
            if (visited.count(currB)) {
                return currB;
            }
            currB = currB->next;
        }
        return nullptr;
    }
};
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        visited = set()
        currA = headA
        while currA:
            visited.add(currA)
            currA = currA.next
        currB = headB
        while currB:
            if currB in visited:
                return currB
            currB = currB.next
        return None
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<>();
        ListNode currA = headA;
        while (currA != null) {
            visited.add(currA);
            currA = currA.next;
        }
        ListNode currB = headB;
        while (currB != null) {
            if (visited.contains(currB)) {
                return currB;
            }
            currB = currB.next;
        }
        return null;
    }
}

Complexity Analysis

Time Complexity: O(m + n)

We traverse list A once to build the set (O(m)), then traverse list B once to check membership (O(n)). Each set insertion and lookup is O(1) average. Total: O(m + n).

Space Complexity: O(m)

We store all m nodes of list A in the hash set. In the worst case, this requires space proportional to the length of list A.

Why This Approach Is Not Efficient

The hash set approach achieves optimal O(m + n) time, which is as fast as we can possibly get — we must examine each node at least once. However, it uses O(m) extra space for the hash set.

The follow-up asks: can we solve this in O(m + n) time with only O(1) extra memory? The key insight is that the two lists differ only in their prefix lengths before the intersection. If we could somehow synchronize two pointers so they reach the intersection node at the same time, we wouldn't need any extra storage. The two-pointer technique achieves exactly this by having each pointer traverse both lists in sequence.

Optimal Approach - Two Pointer Technique

Intuition

The elegant insight behind this approach is based on a simple mathematical fact. Suppose list A has length m and list B has length n, and they share a common tail of length c (starting from the intersection). The unique prefix of A has length a = m - c, and the unique prefix of B has length b = n - c.

If pointer pA starts at head of A and pointer pB starts at head of B, and when either pointer reaches the end of its list it switches to the head of the other list, then:

  • pA travels: a + c + b steps to reach the intersection on its second pass
  • pB travels: b + c + a steps to reach the intersection on its second pass

Both travel the same total distance: a + b + c! So they arrive at the intersection node simultaneously.

If there is no intersection, both pointers will reach null at the same time (after traversing m + n nodes total), and the loop ends naturally.

Think of two runners on tracks that merge. If each runner, after finishing their track, runs the other's track, they will meet at the merge point because they've covered the same total distance.

Step-by-Step Explanation

Let's trace with listA = [4, 1, 8, 4, 5] (m=5) and listB = [5, 6, 1, 8, 4, 5] (n=6), intersecting at node(8). Unique prefix of A: [4, 1] (a=2). Unique prefix of B: [5, 6, 1] (b=3). Shared tail: [8, 4, 5] (c=3).

Step 1: pA → A's node(4), pB → B's node(5). pA ≠ pB.

Step 2: Move both: pA → A's node(1), pB → B's node(6). pA ≠ pB.

Step 3: Move both: pA → A's node(8), pB → B's node(1). pA ≠ pB.

Step 4: Move both: pA → A's node(4), pB → A's node(8). Wait — pB hasn't switched yet. Let me re-trace properly.

  • pA → node(4) in shared tail, pB → B's node(8) which IS node(8) in shared tail. But pA is at node(4) and pB is at node(8) — different nodes. Continue.

Step 5: pA → node(5) end of A, pB → node(4) in shared tail. Different.

Step 6: pA reaches null → switch pA to headB. pB → node(5) end of list. pB reaches null → switch pB to headA.

  • pA → B's node(5), pB → A's node(4)

Step 7: pA → B's node(6), pB → A's node(1). Different.

Step 8: pA → B's node(1), pB → shared node(8). Different.

Step 9: pA → shared node(8), pB → shared node(8). Wait — let me count more carefully.

After the switch: pA traverses B's prefix [5, 6, 1] (3 steps), then arrives at node(8). pB traverses A's prefix [4, 1] (2 steps), then arrives at node(8). Since pA switched first (A is shorter), after the switch pA needs b=3 more steps to reach intersection, and pB needs a=2 more steps. They both end up at the same step count: a + c + b = b + c + a = 2 + 3 + 3 = 8 steps each.

Step 9: pA = node(8), pB = node(8). They are the same node! Return node(8).

Two Pointer Technique — Synchronized Traversal — Watch how two pointers traverse both lists. When one reaches the end, it switches to the other list's head. They meet at the intersection because they cover equal total distances.

Algorithm

  1. Initialize pA at headA and pB at headB.
  2. While pA != pB:
    • If pA is null, switch it to headB. Otherwise, advance pA to pA.next.
    • If pB is null, switch it to headA. Otherwise, advance pB to pB.next.
  3. When the loop exits, pA and pB point to the same node — either the intersection node or null (if no intersection exists).
  4. Return pA (or pB).

Code

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* pA = headA;
        ListNode* pB = headB;
        while (pA != pB) {
            pA = (pA != nullptr) ? pA->next : headB;
            pB = (pB != nullptr) ? pB->next : headA;
        }
        return pA;
    }
};
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        pA, pB = headA, headB
        while pA is not pB:
            pA = pA.next if pA else headB
            pB = pB.next if pB else headA
        return pA
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA;
        ListNode pB = headB;
        while (pA != pB) {
            pA = (pA != null) ? pA.next : headB;
            pB = (pB != null) ? pB.next : headA;
        }
        return pA;
    }
}

Complexity Analysis

Time Complexity: O(m + n)

Each pointer traverses at most m + n nodes (its own list plus the other list). In total, both pointers together visit at most 2(m + n) nodes, which is O(m + n).

Space Complexity: O(1)

We use only two pointer variables regardless of the input size. No hash sets, arrays, or other auxiliary data structures are needed. This is the optimal solution — it matches the O(m + n) time of the hash set approach while reducing space from O(m) to O(1).