Problem Description#

Given the head nodes headA and headB of two singly linked lists, determine whether they intersect (i.e., some node is shared by both linked lists). If they intersect, return the intersection node; otherwise, return null.

1
Input: headA = 4→1→8→4→5
2
      headB = 5→6→1→8→4→5
3
                    ↑
4
                    intersection
5
Output: node 8

The two linked lists meet at node 8, after which they share the 4→5 portion.

Solution Approach#

Code Implementation#

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
typedef struct ListNode {
5
    int val;
6
    struct ListNode *next;
7
} ListNode;
8

9
ListNode* getIntersectionNode(ListNode *headA, ListNode *headB) {
10
    if (!headA || !headB) return NULL;
11

12
    ListNode *pA = headA;
13
    ListNode *pB = headB;
14

15
    // Two pointers traverse alternately
16
    while (pA != pB) {
17
        pA = pA ? pA->next : headB; // pA finishes A then goes to B
18
        pB = pB ? pB->next : headA; // pB finishes B then goes to A
19
    }
20

21
    // Meeting point: intersection or null
22
    return pA;
23
}

1
struct ListNode {
2
    int val;
3
    ListNode *next;
4
    ListNode(int x) : val(x), next(nullptr) {}
5
};
6

7
class Solution {
8
public:
9
    ListNode* getIntersectionNode(ListNode *headA, ListNode *headB) {
10
        if (!headA || !headB) return nullptr;
11

12
        ListNode *pA = headA;
13
        ListNode *pB = headB;
14

15
        // Two pointers traverse alternately
16
        while (pA != pB) {
17
            pA = pA ? pA->next : headB; // pA finishes A then goes to B
18
            pB = pB ? pB->next : headA; // pB finishes B then goes to A
19
        }
20

21
        // Meeting point: intersection or nullptr
22
        return pA;
23
    }
24
};

1
class ListNode {
2
    constructor(val) {
3
        this.val = val;
4
        this.next = null;
5
    }
6
}
7

8
function getIntersectionNode(headA, headB) {
9
    if (!headA || !headB) return null;
10

11
    let pA = headA;
12
    let pB = headB;
13

14
    // Two pointers traverse alternately
15
    while (pA !== pB) {
16
        pA = pA ? pA.next : headB; // pA finishes A then goes to B
17
        pB = pB ? pB.next : headA; // pB finishes B then goes to A
18
    }
19

20
    // Meeting point: intersection or null
21
    return pA;
22
}

Illustrated Process#

1
Linked list A:  a1 → a2
2
                 ↘
3
                   c1 → c2 → c3
4
                 ↗
5
Linked list B:  b1 → b2 → b3

1
pA path: a1 → a2 → c1 → c2 → c3 → b1 → b2 → b3 → ★c1
2
pB path: b1 → b2 → b3 → c1 → c2 → c3 → a1 → a2 → ★c1
3

4
At ★ the two pointers meet, so c1 is the intersection point ✓

1
Linked list A:  1 → 2 → 3
2
Linked list B:  4 → 5

1
pA path: 1 → 2 → 3 → 4 → 5 → null
2
pB path: 4 → 5 → 1 → 2 → 3 → null
3

4
★ Both pointers reach null at the same time ✓

Complexity Analysis#

Key Points#

1. “Walk the path you walked”: pA finishes its own list and then walks B, while pB finishes its own list and then walks A—this design lets the two pointers eliminate the length difference and reach the intersection at the same time
2. Reach null at the same time: If there is no intersection, the two pointers will also reach null at the same time after traversing the same total length, and the loop ends naturally
3. Cannot skip null midway: Some implementations say “jump when reaching null,” which is fine, because acyclic linked lists all end in null
4. Difference from cycle detection: This problem assumes the linked lists are acyclic. If cycles are possible, cycle detection must be done first

Extended Thinking#

• If the linked lists may contain cycles, how do we determine intersection? — This requires case-by-case discussion: both acyclic, one cyclic and one acyclic, both cyclic
• Is there a more intuitive solution? — You can first compute the length difference between the two linked lists, let the pointer of the longer list walk the “difference” steps first, and then walk in sync

Related articles:

• Detect a cycle and find its starting point — another “meeting” logic
• Find the Kth node from the end — a similar idea of “eliminating the length difference”