Intersection of Two Linked Lists

Problem#

Two singly-linked lists may merge at some node and share their suffix. Return that merge node, or nullptr if they don’t intersect.

Examples#

Two lists that share a tail starting at value 8 → return that node.

Constraints#

Lists may be of different lengths; no cycles.

Hints#

Hint 1

If lengths matched, walking in lockstep would find the merge. Lengths don’t match — pad each pointer with the other list.

Approach#

Two pointers a, b start at the two heads. At each step, advance one node; when a pointer reaches null, restart it at the other head. Both pointers traverse exactly lenA + lenB nodes and meet at the merge (or simultaneously hit null if disjoint).

Solution#

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        ListNode *a = headA, *b = headB;
        while (a != b) {
            a = a ? a->next : headB;
            b = b ? b->next : headA;
        }
        return a;
    }
};

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    a, b := headA, headB
    for a != b {
        if a != nil {
            a = a.Next
        } else {
            a = headB
        }
        if b != nil {
            b = b.Next
        } else {
            b = headA
        }
    }
    return a
}

from typing import Optional

class Solution:
    def getIntersectionNode(self, headA: Optional[ListNode], headB: Optional[ListNode]) -> Optional[ListNode]:
        a, b = headA, headB
        while a is not b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a

function getIntersectionNode(headA, headB) {
    let a = headA, b = headB;
    while (a !== b) {
        a = a ? a.next : headB;
        b = b ? b.next : headA;
    }
    return a;
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA, b = headB;
        while (a != b) {
            a = (a != null) ? a.next : headB;
            b = (b != null) ? b.next : headA;
        }
        return a;
    }
}

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

Editorial#

The pointer-swap aligns the effective starting positions: from a’s perspective it walks lenA + lenB nodes total before meeting b, which walks the same. They land on the intersection — or, if no intersection exists, both reach null simultaneously and the loop exits cleanly.

Complexity#

Time: O(n + m).
Space: O(1).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#