# LeetCode 160: Intersection of Two Linked Lists

## Problem Restatement

We are given the heads of two singly linked lists:

```python
headA
headB
```

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

If the lists do not intersect, return:

```python
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

| Item | Meaning |
|---|---|
| Input | `headA` and `headB`, the heads of two singly linked lists |
| Output | The intersecting node, or `None` |
| Intersection | Same node reference, not same value |
| Structure rule | Do not modify either list |
| Cycle rule | There are no cycles |

Example function shape:

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

## Examples

Example 1:

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

The lists intersect at the node with value:

```python
8
```

The shared tail is:

```text
8 -> 4 -> 5
```

Return the node `8`.

Example 2:

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

The lists intersect at the node with value:

```python
2
```

Return the shared node `2`.

Example 3:

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

The lists do not intersect.

Return:

```python
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.

```python
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:

```text
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:

```python
a = headA
b = headB
```

Then loop while the two pointers are different:

```python
while a is not b:
```

Move each pointer forward.

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

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

When the loop ends, return either pointer:

```python
return a
```

It is either the intersection node or `None`.

## Walkthrough

Use:

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

The shared part begins at `c1`.

Pointer `a` walks:

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

Pointer `b` walks:

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

They meet at:

```text
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:

```text
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.

| Metric | Value | Why |
|---|---|---|
| Time | `O(m + n)` | Each pointer walks at most both lists |
| Space | `O(1)` | Only two pointers are used |

## Implementation

```python
# 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:

```python
a = headA
b = headB
```

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

```python
while a is not b:
```

Use identity comparison.

Two nodes with equal values are still different nodes.

Move pointer `a`:

```python
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`:

```python
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.

```python
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

```python
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()
```

| Test | Why |
|---|---|
| Shared tail `[8, 4, 5]` | Standard intersection case |
| Shared tail `[2, 4]` | Different prefix lengths |
| No intersection | Returns `None` |
| Same head | Intersection starts immediately |