LeetCode 160: Intersection of Two Linked Lists

Problem Restatement

We are given the heads of two singly linked lists:

headA
headB

We need to return the node where the two linked lists intersect.

If the lists do not intersect, return:

None

Intersection means the two lists share the same node object in memory. It does not mean two nodes merely have the same value.

The test cases have no cycles, and the linked lists must keep their original structure after the function returns. The custom judge builds the shared linked structure and passes only headA and headB to the solution.

Input and Output

Example function shape:

def getIntersectionNode(headA: ListNode, headB: ListNode) -> Optional[ListNode]:
    ...

Examples

Example 1:

A: 4 -> 1 -> 8 -> 4 -> 5
B: 5 -> 6 -> 1 -> 8 -> 4 -> 5

The lists intersect at the node with value:

8

The shared tail is:

8 -> 4 -> 5

Return the node 8.

Example 2:

A: 1 -> 9 -> 1 -> 2 -> 4
B: 3 -> 2 -> 4

The lists intersect at the node with value:

2

Return the shared node 2.

Example 3:

A: 2 -> 6 -> 4
B: 1 -> 5

The lists do not intersect.

Return:

None

First Thought: Store Visited Nodes

A simple solution is to store every node from list A in a set.

Then scan list B.

The first node from B that appears in the set is the intersection.

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        seen = set()

        cur = headA
        while cur:
            seen.add(cur)
            cur = cur.next

        cur = headB
        while cur:
            if cur in seen:
                return cur
            cur = cur.next

        return None

This works because intersection is based on node identity.

But it uses O(m) extra space, where m is the length of list A.

We can do better.

Key Insight

Suppose list A has length m, and list B has length n.

If two pointers start at the heads, they may reach the intersection at different times because the lists may have different prefix lengths.

The trick is to make both pointers walk the same total distance.

Pointer a starts at headA.

Pointer b starts at headB.

When a reaches the end of list A, send it to headB.

When b reaches the end of list B, send it to headA.

So each pointer walks:

A length + B length

If the lists intersect, the pointers meet at the intersection node.

If they do not intersect, both pointers become None after the same total distance.

Algorithm

Initialize:

a = headA
b = headB

Then loop while the two pointers are different:

while a is not b:

Move each pointer forward.

If a pointer reaches the end, redirect it to the head of the other list.

a = a.next if a else headB
b = b.next if b else headA

When the loop ends, return either pointer:

return a

It is either the intersection node or None.

Walkthrough

Use:

A: a1 -> a2 -> c1 -> c2 -> c3
B: b1 -> b2 -> b3 -> c1 -> c2 -> c3

The shared part begins at c1.

Pointer a walks:

a1 -> a2 -> c1 -> c2 -> c3 -> b1 -> b2 -> b3 -> c1

Pointer b walks:

b1 -> b2 -> b3 -> c1 -> c2 -> c3 -> a1 -> a2 -> c1

They meet at:

c1

The redirection cancels out the length difference between the two list prefixes.

Correctness

If the two lists intersect, then after the intersection node they share the same tail.

Let the part before the intersection in list A have length x.

Let the part before the intersection in list B have length y.

Let the shared tail have length z.

Pointer a walks x + z nodes in list A, then switches to list B and walks y more nodes.

Pointer b walks y + z nodes in list B, then switches to list A and walks x more nodes.

So both pointers walk:

x + y + z

steps before reaching the intersection node.

Therefore, they meet at the first shared node.

If the lists do not intersect, there is no shared node. Pointer a walks all of A and then all of B. Pointer b walks all of B and then all of A. After the same total number of steps, both pointers become None.

So the loop ends with either the intersection node or None.

Complexity

Let m be the length of list A and n be the length of list B.

Implementation

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        a = headA
        b = headB

        while a is not b:
            a = a.next if a else headB
            b = b.next if b else headA

        return a

Code Explanation

We start one pointer at each list head:

a = headA
b = headB

The loop continues until both pointers refer to the same node:

while a is not b:

Use identity comparison.

Two nodes with equal values are still different nodes.

Move pointer a:

a = a.next if a else headB

If a still points to a node, move to the next node.

If a has reached the end, restart it at headB.

Do the symmetric operation for b:

b = b.next if b else headA

When the loop stops, a and b are the same reference.

That reference is either the intersection node or None.

Alternative: Length Alignment

Another valid solution is to compute both list lengths.

Then advance the pointer in the longer list by the length difference.

After that, move both pointers together until they meet.

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        def length(head):
            count = 0
            cur = head

            while cur:
                count += 1
                cur = cur.next

            return count

        lenA = length(headA)
        lenB = length(headB)

        a = headA
        b = headB

        while lenA > lenB:
            a = a.next
            lenA -= 1

        while lenB > lenA:
            b = b.next
            lenB -= 1

        while a is not b:
            a = a.next
            b = b.next

        return a

This also runs in O(m + n) time and O(1) space.

The two-pointer redirection version is shorter because it performs the length alignment implicitly.

Testing

from typing import Optional

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

def build_list(values):
    dummy = ListNode(0)
    cur = dummy

    for value in values:
        cur.next = ListNode(value)
        cur = cur.next

    return dummy.next

def tail(head):
    cur = head
    while cur and cur.next:
        cur = cur.next
    return cur

def run_tests():
    sol = Solution()

    shared = build_list([8, 4, 5])
    a = build_list([4, 1])
    b = build_list([5, 6, 1])
    tail(a).next = shared
    tail(b).next = shared
    assert sol.getIntersectionNode(a, b) is shared

    shared = build_list([2, 4])
    a = build_list([1, 9, 1])
    b = build_list([3])
    tail(a).next = shared
    tail(b).next = shared
    assert sol.getIntersectionNode(a, b) is shared

    a = build_list([2, 6, 4])
    b = build_list([1, 5])
    assert sol.getIntersectionNode(a, b) is None

    shared = build_list([1, 2, 3])
    assert sol.getIntersectionNode(shared, shared) is shared

    print("all tests passed")

run_tests()