160. Intersection of Two Linked Lists (Easy)

Problem

Given the heads of two singly linked lists, return the node at which the two lists intersect. If the two lists have no intersection, return None. The lists must remain structurally intact after the function returns.

Example

• listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], intersect at node with val 8 → node 8
• listA = [2,6,4], listB = [1,5], no intersection → None

LeetCode 160 · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, hash set of visited nodes

Walk list A and store every node object in a set. Walk list B and return the first node found in the set.

Python

def get_intersection_node(headA, headB):
    visited = set()
    cur = headA
    while cur:                    # L1: O(m) walk list A
        visited.add(cur)          # L2: O(1) store node reference
        cur = cur.next
    cur = headB
    while cur:                    # L3: O(n) walk list B
        if cur in visited:        # L4: O(1) set lookup
            return cur
        cur = cur.next
    return None

TypeScript

class ListNode {
    val: number; next: ListNode | null;
    constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
    const visited = new Set<ListNode>();
    let cur = headA;
    while (cur) { visited.add(cur); cur = cur.next; }  // L1-L2: O(m) walk list A
    cur = headB;
    while (cur) {                 // L3: O(n) walk list B
        if (visited.has(cur)) return cur;  // L4: O(1) set lookup
        cur = cur.next;
    }
    return null;
}

Swift

final class Solution {
func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
        var seen: Set<ObjectIdentifier> = []
        var current = headA
        while let node = current {
            seen.insert(ObjectIdentifier(node))
            current = node.next
        }
        current = headB
        while let node = current {
            if seen.contains(ObjectIdentifier(node)) { return node }
            current = node.next
        }
        return nil
    }
}

Where the time goes, line by line

Variables: m = len(listA), n = len(listB).

Line	Per-call cost	Times executed	Contribution
L1/L2 (walk A)	$O(1)$	m	$O(m)$
L3/L4 (walk B)	$O(1)$	n	$O(n)$

Complexity

• Time: $O(m + n)$
• Space: $O(m)$ for the visited set

Correct but uses $O(m)$ extra memory.

Approach 2: Two pointers, equal-distance trick (optimal)

Two pointers pA and pB start at headA and headB. When either reaches the end of its list, redirect it to the other list’s head. They meet at the intersection after at most m + n steps.

Why it works: if the lists intersect, pA travels a + c + b total steps and pB travels b + c + a total steps (where a = len of A before shared tail, b = len of B before shared tail, c = shared tail length). Both totals equal a + b + c, so they arrive at the intersection simultaneously.

If there is no intersection, both pointers reach None at the same time (each having traveled a + b steps), ending the loop.

Python

def get_intersection_node(headA, headB):
    pA, pB = headA, headB
    while pA is not pB:              # L1: loop until equal (both None, or shared node)
        pA = pA.next if pA else headB  # L2: O(1) advance; redirect at end
        pB = pB.next if pB else headA  # L3: O(1) advance; redirect at end
    return pA                         # L4: intersection node, or None

TypeScript

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
    let pA: ListNode | null = headA;
    let pB: ListNode | null = headB;
    while (pA !== pB) {              // L1: loop until equal (both null, or shared node)
        pA = pA ? pA.next : headB;  // L2: O(1) advance; redirect at end
        pB = pB ? pB.next : headA;  // L3: O(1) advance; redirect at end
    }
    return pA;                       // L4: intersection node, or null
}

Swift

final class Solution {
func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
        var left = headA
        var right = headB
        while !sameNode(left, right) {
            left = left == nil ? headB : left?.next
            right = right == nil ? headA : right?.next
        }
        return left
    }
}

Where the time goes, line by line

Variables: m = len(listA), n = len(listB).

Line	Per-call cost	Times executed	Contribution
L1 (loop guard)	$O(1)$	at most m+n	$O(m+n)$
L2/L3 (advance + redirect)	$O(1)$	at most m+n	$O(m+n)$ ← dominates
L4 (return)	$O(1)$	1	$O(1)$

Complexity

• Time: $O(m + n)$, each pointer traverses at most m + n nodes before meeting.
• Space: $O(1)$.

Path diagram

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

pA path: a1, a2, c1, c2, c3, b1, b2, b3, [c1]  <- meet here
pB path: b1, b2, b3, c1, c2, c3, a1, a2, [c1]  <- meet here

Both pointers travel 8 steps (a=2, b=3, c=3: 2+3+3=8) before landing on c1 simultaneously.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Key takeaways

• The trick is that both pointers travel the same total distance (m + n) regardless of where the intersection is.
• No length calculation needed; the redirect handles the alignment automatically.
• The pA is not pB check works for the no-intersection case: both pointers become None at step m + n and the loop exits.

Test cases

Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def get_intersection_node(headA, headB):
    pA, pB = headA, headB
    while pA is not pB:
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA
    return pA

def _run_tests():
    # Shared tail: A=[4,1,8,4,5], B=[5,6,1,8,4,5], intersect at 8
    shared = ListNode(8, ListNode(4, ListNode(5)))
    headA = ListNode(4, ListNode(1, shared))
    headB = ListNode(5, ListNode(6, ListNode(1, shared)))
    assert get_intersection_node(headA, headB) is shared

    # No intersection
    a = ListNode(2, ListNode(6, ListNode(4)))
    b = ListNode(1, ListNode(5))
    assert get_intersection_node(a, b) is None

    # Both empty
    assert get_intersection_node(None, None) is None

    # One empty
    assert get_intersection_node(ListNode(1), None) is None

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

class ListNode {
    val: number; next: ListNode | null;
    constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
    let pA: ListNode | null = headA, pB: ListNode | null = headB;
    while (pA !== pB) { pA = pA ? pA.next : headB; pB = pB ? pB.next : headA; }
    return pA;
}

// Shared tail: A=[4,1,8,4,5], B=[5,6,1,8,4,5], intersect at 8
const shared = new ListNode(8, new ListNode(4, new ListNode(5)));
const headA = new ListNode(4, new ListNode(1, shared));
const headB = new ListNode(5, new ListNode(6, new ListNode(1, shared)));
console.assert(getIntersectionNode(headA, headB) === shared);

// No intersection
const a = new ListNode(2, new ListNode(6, new ListNode(4)));
const b = new ListNode(1, new ListNode(5));
console.assert(getIntersectionNode(a, b) === null);

// Both empty
console.assert(getIntersectionNode(null, null) === null);

// One empty
console.assert(getIntersectionNode(new ListNode(1), null) === null);

console.log("all tests pass");

Related topics

• 141. Linked List Cycle, another two-pointer trick on linked lists
• 206. Reverse Linked List, pointer fundamentals

Related concepts

• Two Pointers, the two index invariant that shrinks or coordinates positions without nested loops.
• Linked List Pointer Rewiring, the link editing pattern for changing node order without losing the chain.