EasyLinked ListTwo PointersHash Table

Intersection of Two Linked Lists

1 approach, code in every language

You are given the heads of two singly linked lists. Return the exact node at which the two lists first join together, or return null if they never meet.

Intersection is defined by reference, not by value: the two lists share the same physical node object from the meeting point onward, so their tails are identical. The original list structures must be left unchanged.

Example 1

Input: listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

Output: Reference of the node with value 8

Both lists lead into the same node valued 8 and share every node after it, so that node is the intersection.

Example 2

Input: listA = [2,6,4], listB = [1,5]

Output: null

The two lists have no node in common, so the answer is null.

Constraints

The number of nodes of listA is in the range [1, 3 * 10^4].
The number of nodes of listB is in the range [1, 3 * 10^4].
1 <= Node.val <= 10^5
The two lists either intersect at exactly one node or do not intersect at all.

Two Pointers with Head Switch

Walk both lists and swap starting heads so the pointers align at the junction.

Loading animation…

Intuition

Let the two lists have lengths a and b with a shared suffix of length c. If a pointer that finishes list A continues from the head of list B, and vice versa, then each pointer travels exactly a + b nodes before running out. Because both pointers cover the same combined distance, they arrive at the intersection node at the very same step. If the lists never intersect, both pointers reach null at the same time and the comparison ends the loop with a null answer. This elegantly cancels out the length difference without measuring either list explicitly.

Algorithm walkthrough

1Set pointer a to headA and pointer b to headB.
2Loop while a and b are not the same node reference.
3Advance a to a.next, but when a is null redirect it to headB instead.
4Advance b to b.next, but when b is null redirect it to headA instead.
5After at most len(A) + len(B) steps the pointers are equal; return that node (the intersection or null).

Implementation

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: 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

Time

O(a + b)

Space

O(1)

Each pointer walks both lists once; no extra data structures are needed.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Linked List

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free