[/dsa/leetcode]

160 - Intersection of Two Linked Lists

Friday, 18 September 2026

<easy> [problem]

Two walkers that switch lists when they fall off the end, so both cover the same total distance and land on the shared node together.

{linked list}{two pointers}{hash table}

Problem

Given the heads of two singly linked lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection, return null.

The test cases are generated such that there are no cycles anywhere in the structure, and the lists must retain their original structure after the function returns.

Input: A = [4,1,8,4,5], B = [5,6,1,8,4,5], intersect at 8
Output: 8

Input: A = [1,9,1,2,4], B = [3,2,4], intersect at 2
Output: 2

Input: A = [2,6,4], B = [1,5], no intersection
Output: null

Constraints:

  • The number of nodes of listA is in the range [1, 10^4]
  • The number of nodes of listB is in the range [1, 10^4]
  • 1 <= Node.val <= 10^5

Follow-up: could you write a solution that runs in O(m + n) time and uses O(1) memory?

Approach

Intersection here means the same node, not the same value.

The obvious solutions both give something up. Put every node of A in a hash set and walk B looking for a hit: O(m + n) time but O(m) space. Or measure both lengths, advance the longer list by the difference so the two are equally far from the end, then walk in step: O(1) space, but it takes two passes and some length bookkeeping.

The trick avoids both. Call the part of A before the junction a1, the part of B before it b1, and the shared tail c. The reason a plain lockstep walk fails is that a1 and b1 differ, so the pointers are never the same distance from the junction. Fix that by making each pointer walk its own list, then the other one. Now the distance to the junction is a1 + b1 + c either way, the same number for both, so they arrive at the same time no matter how lopsided the lists are.

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;
    }
};
A = [1,9,1,2,4], B = [3,2,4], junction at 2

t        0     1     2     3     4     5     6     7
a        1     9     1     2     4  null     3     2
b        3     2     4  null     1     9     1     2
                                                meet at 2

a != b compares pointers, so the walk stops on the shared node itself rather than on a matching value. At t=3 a is already sitting on the junction, but b is elsewhere, so nothing fires early.

Why it terminates when there’s no intersection. Each pointer steps onto nullptr at the end of a list before switching, and that null is what saves us. a is null after m steps, b after n, and both are null again at step m + n + 1 — at the same time. The loop sees a == b == nullptr, exits, and returns nullptr, which is the right answer.

  • time: O(m + n) - each pointer walks both lists once
  • space: O(1) - two pointers, neither list is modified
quantinium © 2026