160. Intersection of Two Linked Lists

Problem¶

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 it 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.

Python 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

Comment on my solution¶

Not provided.