Difficulty: 🟢 Easy
Topics: Hash Table, Linked List, Two Pointers

Solution

LeetCode 160, Intersection of Two Linked Lists

Problem Understanding

This problem asks us to determine whether two singly linked lists share a common node, and if they do, return the exact node where the intersection begins.

The important detail is that an intersection is based on node reference, not node value. Two nodes containing the same value are not considered the same unless they are literally the same object in memory.

For example, consider these two lists:

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

The lists intersect at the node with value 8, because both lists eventually point to the exact same node object. From that point onward, every remaining node is shared between the two lists.

The input provides two head pointers:

headA, the head of the first linked list
headB, the head of the second linked list

The expected output is:

The intersecting node if one exists
null if the lists never intersect

The problem guarantees that:

There are no cycles in either list
The linked list structure must remain unchanged
The lists may have different lengths
The intersection, if it exists, forms a shared suffix

The constraints allow up to 3 * 10^4 nodes in each list. This size is large enough that inefficient quadratic solutions may become problematic. The follow up specifically asks for an O(m + n) time solution using only O(1) extra memory.

Several edge cases are important:

One or both lists may contain only one node
The lists may not intersect at all
The intersection could occur at the head itself
One list may be much longer than the other
The shared tail may contain only a single node

A naive implementation that compares values instead of node references would produce incorrect results.

Approaches

Brute Force Approach

The brute force solution compares every node in list A against every node in list B.

For each node in the first list, we traverse the second list completely and check whether the two node references are identical.

If we ever find:

nodeA == nodeB

then we have found the intersection node.

This approach is correct because every possible pair of nodes is checked. If an intersection exists, eventually the matching references will be compared.

However, the time complexity is poor. If list A has m nodes and list B has n nodes, then in the worst case we perform m * n comparisons.

With lists containing tens of thousands of nodes, this becomes inefficient.

Optimal Two Pointer Approach

The key observation is that after two linked lists intersect, all remaining nodes are shared.

Suppose:

List A length is m
List B length is n
Shared tail length is k

Then:

Unique portion of A is m - k
Unique portion of B is n - k

The challenge is aligning the traversal so both pointers reach the intersection at the same time.

A clever trick solves this elegantly:

Pointer A traverses list A, then switches to list B
Pointer B traverses list B, then switches to list A

Eventually, both pointers travel exactly the same total distance:

m + n

If an intersection exists, they meet there.

If no intersection exists, both eventually become null simultaneously.

This works without computing lengths explicitly and uses only constant extra memory.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m × n)	O(1)	Compare every node in A against every node in B
Optimal	O(m + n)	O(1)	Two pointers switch lists to equalize traversal distance

Algorithm Walkthrough

Optimal Two Pointer Algorithm

Initialize two pointers:

pointerA = headA
pointerB = headB

Each pointer starts at the head of its respective list. 2. Traverse both lists simultaneously.

At each iteration:

Move pointerA one step forward
Move pointerB one step forward

When a pointer reaches the end of its list:

Redirect it to the head of the opposite list

Specifically:

If pointerA becomes null, set it to headB
If pointerB becomes null, set it to headA

Continue until:

pointerA == pointerB

This equality works because linked list intersection depends on node identity. 5. Return the meeting node.

If the lists intersect, this node is the first shared node.

If they do not intersect, both pointers eventually become null, and the algorithm returns null.

Why it works

Each pointer traverses exactly the same combined distance:

Length(A) + Length(B)

If one list is longer, switching lists compensates for the length difference. After both pointers have traversed the unique portions of each list, they become aligned relative to the shared tail.

Because both pointers move at the same speed and traverse equal total distances, they must either:

Meet at the intersection node
Reach null simultaneously if no intersection exists

This invariant guarantees correctness.

Python Solution

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

from typing import Optional

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

        pointerA = headA
        pointerB = headB

        while pointerA != pointerB:
            if pointerA is None:
                pointerA = headB
            else:
                pointerA = pointerA.next

            if pointerB is None:
                pointerB = headA
            else:
                pointerB = pointerB.next

        return pointerA

The implementation begins by creating two pointers, one for each linked list.

The main loop continues until the two pointers reference the same node. Since node equality in linked lists is reference equality, this correctly detects the actual intersection node.

Inside the loop, each pointer advances normally through its current list. When a pointer reaches the end, it switches to the other list's head.

This switching behavior is the core idea of the algorithm. It ensures both pointers eventually traverse identical total distances, eliminating any length imbalance between the lists.

When the loop exits, there are only two possibilities:

Both pointers point to the intersection node
Both pointers are None

Returning pointerA handles both cases correctly.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    pointerA := headA
    pointerB := headB

    for pointerA != pointerB {
        if pointerA == nil {
            pointerA = headB
        } else {
            pointerA = pointerA.Next
        }

        if pointerB == nil {
            pointerB = headA
        } else {
            pointerB = pointerB.Next
        }
    }

    return pointerA
}

The Go implementation follows the exact same logic as the Python version.

The primary language-specific difference is the use of nil instead of None.

Pointer comparisons in Go naturally compare memory addresses, which is exactly what we need for detecting linked list intersection.

No special handling for integer overflow or slices is necessary because the algorithm only manipulates linked list pointers.

Worked Examples

Example 1

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

Shared portion:

8 -> 4 -> 5

Step	pointerA	pointerB
1	4	5
2	1	6
3	8	1
4	4	8
5	5	4
6	null	5
7	5	null
8	6	4
9	1	1
10	8	8

At step 10, both pointers reference the exact same node.

Return node with value 8.

Example 2

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

Shared portion:

2 -> 4

Step	pointerA	pointerB
1	1	3
2	9	2
3	1	4
4	2	null
5	4	1
6	null	9
7	3	1
8	2	2

The pointers meet at the node with value 2.

Example 3

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

There is no shared node.

Step	pointerA	pointerB
1	2	1
2	6	5
3	4	null
4	null	2
5	1	6
6	5	4
7	null	null

Both pointers become null simultaneously.

Return null.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m + n)	Each pointer traverses each list at most once
Space	O(1)	Only two pointer variables are used

The algorithm is linear because each pointer performs at most two full traversals, one through each list. No nested traversal occurs.

The memory usage remains constant regardless of input size because no auxiliary data structures are allocated.

Test Cases

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

class Solution:
    def getIntersectionNode(self, headA, headB):
        pointerA = headA
        pointerB = headB

        while pointerA != pointerB:
            pointerA = headB if pointerA is None else pointerA.next
            pointerB = headA if pointerB is None else pointerB.next

        return pointerA

solution = Solution()

# Test 1: Standard intersection
shared = ListNode(8)
shared.next = ListNode(4)
shared.next.next = ListNode(5)

a1 = ListNode(4)
a1.next = ListNode(1)
a1.next.next = shared

b1 = ListNode(5)
b1.next = ListNode(6)
b1.next.next = ListNode(1)
b1.next.next.next = shared

assert solution.getIntersectionNode(a1, b1) == shared  # standard intersection

# Test 2: Intersection near tail
shared2 = ListNode(2)
shared2.next = ListNode(4)

a2 = ListNode(1)
a2.next = ListNode(9)
a2.next.next = ListNode(1)
a2.next.next.next = shared2

b2 = ListNode(3)
b2.next = shared2

assert solution.getIntersectionNode(a2, b2) == shared2  # shared tail

# Test 3: No intersection
a3 = ListNode(2)
a3.next = ListNode(6)
a3.next.next = ListNode(4)

b3 = ListNode(1)
b3.next = ListNode(5)

assert solution.getIntersectionNode(a3, b3) is None  # no intersection

# Test 4: Same exact list
shared4 = ListNode(1)
shared4.next = ListNode(2)

assert solution.getIntersectionNode(shared4, shared4) == shared4  # same head

# Test 5: Single node intersection
shared5 = ListNode(7)

assert solution.getIntersectionNode(shared5, shared5) == shared5  # one shared node

# Test 6: Different lengths with no intersection
a6 = ListNode(1)
a6.next = ListNode(2)
a6.next.next = ListNode(3)

b6 = ListNode(4)

assert solution.getIntersectionNode(a6, b6) is None  # unequal lengths

# Test 7: Intersection at last node only
shared7 = ListNode(10)

a7 = ListNode(1)
a7.next = ListNode(2)
a7.next.next = shared7

b7 = ListNode(3)
b7.next = shared7

assert solution.getIntersectionNode(a7, b7) == shared7  # intersection at tail

Test	Why
Standard intersection	Verifies normal shared tail behavior
Intersection near tail	Ensures algorithm handles different prefix lengths
No intersection	Confirms correct null return
Same exact list	Tests intersection at head
Single node intersection	Validates smallest possible intersecting structure
Different lengths with no intersection	Ensures switching logic terminates correctly
Intersection at last node only	Tests minimal shared suffix

Edge Cases

The Lists Do Not Intersect

This is one of the most important edge cases because an incorrect implementation may enter an infinite loop.

For non intersecting lists, both pointers eventually traverse both lists completely and become null at the same time. Since the loop condition checks:

pointerA != pointerB

the loop terminates correctly when both are None.

The Intersection Occurs at the Head

If both head pointers already reference the same node, the lists intersect immediately.

In this case:

pointerA == pointerB

is true before the loop even begins, so the algorithm instantly returns the head node without unnecessary traversal.

One List Is Much Longer Than the Other

Large length differences often cause bugs in naive pointer synchronization approaches.

The pointer switching technique automatically compensates for the imbalance. Each pointer traverses both lists exactly once, ensuring they align correctly before entering the shared suffix.

This eliminates the need to explicitly compute lengths or manually advance one pointer ahead of the other.

LeetCode 160 - Intersection of Two Linked Lists