Intersection of Two Linked Lists — Editorial

Opening the reading…

Intuitionwhy changing lists removes the length mismatch

If two singly linked lists intersect, they share every node from the first common node to the tail. The only reason two pointers miss that node when they start at the heads is that the lists may have different-length prefixes before the shared suffix. A pointer on the longer prefix reaches the shared part later than a pointer on the shorter prefix.

Give each pointer a fair chance to walk both lists. When pointer a leaves list A, continue it from headB; when pointer b leaves list B, continue it from headA. Pointer a then travels lengthA plus lengthB, and pointer b travels lengthB plus lengthA. Their prefix imbalance cancels, so they either meet at the first shared node or become null together.

DIAGRAM — NOT DRAWN YET

Show list A across the top with its unique prefix leading into an intersection node, followed by a shared suffix. Show list B below with a different-length unique prefix leading into that same intersection node and suffix. Mark pointer a at headA and pointer b at headB, then draw curved arrows from each list's null endpoint to the other list's head. The picture makes clear that the pointers exchange prefixes and therefore travel equal total distances.

Approach

Return null immediately if either head is null, because an empty list cannot share a node with a non-empty list and the loop should not dereference an absent head.

Set pointer a to headA and pointer b to headB, because each pointer must first preserve the natural order of its own list.

Continue while a and b refer to different nodes, not merely while their values differ, because intersection means the exact same node object, while equal values can occur in separate nodes.

When a reaches null, redirect it to headB; otherwise advance it to its next node. This gives a the path through both lists without changing either list's links.

When b reaches null, redirect it to headA; otherwise advance it to its next node. Applying the same rule symmetrically is what makes their total travelled distances equal.

Stop when a equals b. The value may be equal at many unrelated nodes, but pointer equality identifies the first shared node or the shared null endpoint.

Return a, which is either the intersection node or null; no links are changed, so the original linked structure remains intact.

Complexitythe two traversals do not revisit a list more than once per pointer

MEASURE	BOUND	WHY
Time	O(m + n)	Each pointer traverses at most list A followed by list B, or list B followed by list A. Thus each pointer advances through at most m + n nodes, and the loop performs no repeated pass beyond those two traversals.
Space	O(1) extra	Only two node pointers are stored, regardless of the lengths or shapes of the lists. The returned node is required output and is not extra storage; the lists are acyclic, so there is no cycle-dependent memory cost.

Here m is the number of nodes in list A and n is the number of nodes in list B.

Annotated solutionC++ · two pointers · redirecting at null balances the prefixes

CPPEach pointer walks its own list, then the other list, until both references match.

#include <cstddef>

using namespace std;

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        if (!headA || !headB) return nullptr;

        ListNode* a = headA;
        ListNode* b = headB;

        while (a != b) {
            a = a ? a->next : headB;
            b = b ? b->next : headA;
        }

        return a;
    }
};

The conditional assignments are the whole balancing mechanism. A normal next step preserves the list traversal, while the null case switches lists exactly once for that pointer. The loop compares pointers before dereferencing them, so the same condition handles both outcomes: a real shared node stops the loop, and two null pointers stop it when no intersection exists.

The length-alignment alternativea different arrangement with the same O(1) space

You can first count both lengths, advance the pointer in the longer list by the difference, and then walk both pointers together. This is not an asymptotic optimisation: it still takes O(m + n) time and O(1) extra space. It is a reasonable choice when explicitly aligning suffixes feels clearer, while the redirecting version avoids separate length bookkeeping.

CPPCount both lists, align their remaining distances, then compare node references in lockstep.

#include <cstddef>

using namespace std;

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        int lengthA = length(headA);
        int lengthB = length(headB);

        ListNode* a = headA;
        ListNode* b = headB;

        if (lengthA > lengthB) {
            advance(a, lengthA - lengthB);
        } else {
            advance(b, lengthB - lengthA);
        }

        while (a != b) {
            a = a->next;
            b = b->next;
        }

        return a;
    }

private:
    int length(ListNode* node) {
        int result = 0;
        while (node) {
            ++result;
            node = node->next;
        }
        return result;
    }

    void advance(ListNode*& node, int steps) {
        while (steps > 0) {
            node = node->next;
            --steps;
        }
    }
};