160. Intersection of Two Linked Lists

Reformulated question¶

Given two singly linked lists, return the first node that is shared by reference by both lists, or None if they do not intersect.

Intersection means the same node object, not equal values.

Example:

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

shared node = 8

Key trick¶

Use two pointers that swap to the other list when they reach the end.

Each pointer traverses m + n nodes.
If the lists intersect, they meet at the shared node.
If not, both become None at the same time.

Trap¶

Comparing node.val instead of node identity.
Using extra memory when \(O(1)\) space is required.
Modifying the lists, which is forbidden.
Forgetting that different nodes can have the same value.

Why is this question interesting?¶

It tests whether you recognize intersection by reference, not by value, and whether you can turn an alignment problem into a clean \(O(m+n)\), \(O(1)\) two-pointer solution.

Solution¶

from typing import Optional
from utils import ListNode


class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        # Two pointers traverse both lists.
        # When one reaches the end, jump it to the other head.
        # This equalizes path lengths without extra memory.
        p1, p2 = headA, headB

        while p1 is not p2:
            p1 = headB if p1 is None else p1.next
            p2 = headA if p2 is None else p2.next

        return p1

Pytest tests¶

import pytest

from utils import list_build, list_find


def make_lists(a_vals, b_vals, shared_vals=None, shared_idx_a=None, shared_idx_b=None):
    # Build two lists that optionally share a tail by node identity.
    if shared_vals is None:
        return list_build(a_vals), list_build(b_vals)

    shared_head = list_build(shared_vals)

    headA = list_build(a_vals)
    if headA is None:
        headA = shared_head
    else:
        cur = headA
        while cur.next:
            cur = cur.next
        cur.next = shared_head

    headB = list_build(b_vals)
    if headB is None:
        headB = shared_head
    else:
        cur = headB
        while cur.next:
            cur = cur.next
        cur.next = shared_head

    return headA, headB


@pytest.mark.parametrize(
    "headA, headB, expected_val",
    [
        (None, None, None),
        (list_build([1]), None, None),
        (None, list_build([1]), None),
        (list_build([1, 2, 3]), list_build([4, 5]), None),
        (list_build([2, 6, 4]), list_build([1, 5]), None),
        (
            (lambda:
                (lambda a, b: (a, b))(
                    list_build([4, 1]),
                    None,
                )
            )(),
            None,
            None,
        ),
    ],
)
def test_getIntersectionNode_no_intersection(headA, headB, expected_val):
    sol = Solution()
    assert sol.getIntersectionNode(headA, headB) is None


@pytest.mark.parametrize(
    "a_prefix, b_prefix, shared, expected",
    [
        ([4, 1], [5, 6, 1], [8, 4, 5], 8),
        ([1, 9, 1], [3], [2, 4], 2),
        ([7], [8, 9, 10], [11], 11),
        ([], [1, 2], [3, 4, 5], 3),
    ],
)
def test_getIntersectionNode_with_intersection(a_prefix, b_prefix, shared, expected):
    # Build shared tail once so identity is actually shared.
    shared_head = list_build(shared)

    headA = list_build(a_prefix)
    if headA is None:
        headA = shared_head
    else:
        cur = headA
        while cur.next:
            cur = cur.next
        cur.next = shared_head

    headB = list_build(b_prefix)
    if headB is None:
        headB = shared_head
    else:
        cur = headB
        while cur.next:
            cur = cur.next
        cur.next = shared_head

    sol = Solution()
    node = sol.getIntersectionNode(headA, headB)
    assert node is not None
    assert node.val == expected
    assert node is shared_head