DSA sheet · Linked List · Basic operations pattern

Intersection of Two Linked Lists

Two linked lists start separately and, at some node, join and share the same tail. We must find that joining node. The teacher uses a running race picture to think of two fair ways to make two pointers arrive at the joining node at the same moment: first by giving the longer list a head start (length difference), then by letting each runner also run the other's track (switching heads). The second one is the classic 4-line answer, and the race idea behind it shows up again in many pointer problems.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Linked list basics you need for this page
• Part A · Length-difference approach (the fair head start)
• Part B · Switch-heads approach (run both tracks)
• Part C · Revision page

Part 0 · Before starting

What is a linked list node?

A linked list is a chain of small boxes called nodes. Each node holds two things: a value (val) and a link to the next node (next). The last node's next is None, which means "the chain ends here".

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val      # the number stored in this node
        self.next = next    # the next node, or None at the end

[4] → [1] → [8] → [4] → [5] → None
 ↑
head

• head is a variable that points to the first node. It is the only way into the list. Lose it and the whole list is gone.
• Walking the list means starting a helper pointer at the head and repeating curr = curr.next until curr becomes None. We use a helper (an "alias") so the real head stays safe.
• No index access. In an array you can jump to position i straight away. A linked list has no positions stored anywhere. To reach the i-th node you must walk i steps from the head, so reaching position i costs O(i), and O(n) in the worst case.
• Save next before changing a pointer. If you overwrite node.next, the rest of the chain is lost unless you saved it first. (This page never rewires a pointer, it only walks. But keep this rule in mind for every other list problem.)

A node is not its value: identity vs value

This is the key idea for this page. Two different nodes can store the same value. A node is a separate object living at its own place in memory (its address). So "the same node" means the same object, not "a node with the same number".

In Python, a is b checks "are these the very same object?". a.val == b.val only checks "do they hold the same number?". For intersection we need is.

What does "two lists intersect" look like?

headA →             [4] → [1] ─┐
                               ├→ [8] → [4] → [5] → None
headB → [5] → [6] → [1] → [2] ─┘

From the node 8 onwards, both lists use the very same nodes. Node 8 is stored once in memory. Node 1 of list A and node 2 of list B both have .next pointing to it. So once two lists meet, they can never split again: a node has only one next. The shape is a Y, never an X.

Part A · Length-difference approach

LeetCode 160 · Intersection of Two Linked Lists

1The question in simple words

You get the heads of two singly linked lists, headA and headB. If the lists join at some node, return that node (the first shared one). If they never join, return None.

• We return the node, not its value. Returning the node 8 automatically hands back 8 → 4 → 5, because the nodes are linked.
• LeetCode's example 1: A = 4 → 1 → 8 → 4 → 5, B = 5 → 6 → 1 → 8 → 4 → 5, and the answer is the node with value 8.
• We must not change the lists. They should look the same after our function runs.

2What the constraints tell us

• m (length of A) and n (length of B) can each be up to 3 × 10⁴.
• The obvious brute force is to take every node of A and compare it with every node of B. That is m × n comparisons = 3×10⁴ × 3×10⁴ = 9 × 10⁸. Above roughly 10⁸ operations we expect TLE (Time Limit Exceeded). So the teacher rules out O(n²) at once: we need a linear solution, something like O(m + n).
• Both lists have at least 1 node, so the heads are never None at the start. (Our code still works if one is empty.)

3Intuition: a fair race

Put one runner on each list: pointer a starts at headA, pointer b starts at headB. Both move one node per step. We want them to stand on the same node at the same moment, because the first time that happens is the joining point.

The problem: the lists have different lengths before they join. In the picture above, A has 2 nodes before the join and B has 4. If both start together, a reaches node 8 after 2 steps, but b needs 4. They pass through node 8 at different times and never meet there.

The teacher's picture: in a real race, every runner must get a track of the same length, otherwise the result means nothing. So the longer list's runner gets moved forward first. If B is longer by 2, move b 2 steps ahead, then start the race. Now both runners have the same distance left to the finish (None), and so the same distance left to the joining node.

4Building the logic from examples

First idea: store the values and look for a match. Why it fails

A natural first thought: walk list A, save all its values, then walk list B and stop at the first value that was already seen. Look at the example: list B's first node is 5, and list A contains a 5 at its end. List A also has a 4 at the front and another 4 after the 8. A value match would report the wrong node.

Second idea: when do we know we found the answer?

When a and b point to the same node at the same time. That can only happen at the joining node or after it, and the first time it happens is exactly the joining node. So the whole job is to make them arrive at the same time.

Count both lengths, then give the longer one a head start

Take the teacher's board example: A has length 5 (2 own nodes + 3 shared), B has length 7 (4 own nodes + 3 shared).

headA →             [4] → [1] ─┐
                               ├→ [8] → [4] → [5] → None
headB → [5] → [6] → [1] → [2] ─┘
         length A = 5,  length B = 7,  difference = 2

The shared tail is the same for both, so the whole difference (2) comes from the parts before the join. Move b forward 2 nodes. Now b sits on B's 3rd node (value 1) and a sits on A's 1st node (value 4). Each has exactly 2 nodes left before node 8. Walk both together: after 1 step they are on (1, 2) → different nodes. After 2 steps both are on node 8 → same node, return it.

5Approach steps

1. Walk A with an alias and count its length lenA. Do the same for B to get lenB.
2. Reset the aliases: a = headA, b = headB.
3. While A is longer, move a one step and reduce lenA. While B is longer, move b one step and reduce lenB.
4. Now both have the same number of nodes left. While a and b are different nodes, move both one step.
5. Return a: the joining node, or None if they only met at the end.

6Code (Python)

class Solution:
    def getIntersectionNode(self, headA, headB):
        lenA, lenB = 0, 0
        a, b = headA, headB

        while a:                 # count length of A
            lenA += 1
            a = a.next
        while b:                 # count length of B
            lenB += 1
            b = b.next

        a, b = headA, headB      # back to the start line

        while lenA > lenB:       # A is longer: give it the head start
            a = a.next
            lenA -= 1
        while lenB > lenA:       # B is longer: give it the head start
            b = b.next
            lenB -= 1

        while a is not b:        # same distance left: run together
            a = a.next
            b = b.next
        return a                 # joining node, or None

7Code line by line

8Dry run

Nodes: A's own nodes are a1(4), a2(1). B's own nodes are b1(5), b2(6), b3(1), b4(2). Shared nodes are c1(8), c2(4), c3(5).

Snapshot after the head start (step 4):

                     a
headA →             [4] → [1] ─┐
                               ├→ [8] → [4] → [5] → None
headB → [5] → [6] → [1] → [2] ─┘
                     b

Snapshot at step 7, both on the same node:

headA →             [4] → [1] ─┐
                               ├→ [8] → [4] → [5] → None
headB → [5] → [6] → [1] → [2] ─┘   ↑
                                  a, b

Notice the 1 in A and the 1 in B: same value, different nodes. If the runners had ever stood on those two 1s together, a value check would have answered wrongly. Comparing nodes avoids that.

9Complexity & remember

• Time: m steps to count A, n steps to count B, then the head start plus the joint walk, which is at most the longer length again. The teacher adds it up as m + n + max(m, n). If m is the larger, that is about O(2m + n); if both are about n, it is about 3n. Still linear, so it passes.
• Space O(1): just two pointers and two counters.

Part B · Switch-heads approach

1The question (same as Part A)

Same input, same output: return the first shared node, or None. The only goal now is to do it in fewer passes: the teacher asks whether we can get from about 3n down to about 2n, with no counting at all.

2What the constraints tell us

• Still up to 3 × 10⁴ nodes each, so O(m + n) is what we want. Part A was already linear; this part is an improvement in the constant (3n → 2n) and in code length.
• We still must not modify the lists, and we still want O(1) extra space.

3Intuition: make both runners run the same total track

In Part A we made the race fair by cutting the longer track (head start). Here is the other way to make it fair, without knowing any lengths: let each runner run both tracks.

• Runner a first runs track A. When it reaches the end, it jumps to the start of track B and keeps running.
• Runner b first runs track B. When it reaches the end, it jumps to the start of track A and keeps running.

Now both run track A + track B in total, just in a different order. The teacher's numbers: lengths 4 and 6 → one runs 4 + 6 = 10, the other runs 6 + 4 = 10. Same total. Same total means they end at the same moment, and as we'll see, they also reach the joining node at the same moment.

4Why switching heads makes both walk the same distance

Split each list into its parts:

      ←── x ──→            (A's own part: x nodes)
headA →  ● → ● ─┐
                ├→ ● → ● → ● → None
headB → ● → ● ─┘   ←─── z ───→   (shared tail: z nodes)
      ←─ y ─→                (B's own part: y nodes)

length of A:  m = x + z          length of B:  n = y + z

Follow each runner until it first reaches the joining node:

The two totals are the same numbers added in a different order, so they are equal. That is the whole proof. After exactly x + y + z + 1 steps, both runners stand on the joining node together.

• Could they meet earlier, at a wrong node? No. Before that moment, at least one of them is still on a node that belongs only to one list, or they are both in the shared part but at different distances. The very first time they are on the same node is the join. (If x = y, they even meet during the first pass, before anyone switches. That's fine too.)
• What is the +1? In the code, falling off the end costs one loop step: the runner first becomes None, and only on the next step does it jump to the other head. Both runners pay this one step, so it doesn't break the equality.

And when the lists never join?

Then z = 0, so there is no shared node to meet at. Runner a walks m nodes, becomes None, switches, walks n nodes, becomes None again. Runner b walks n, None, switches, walks m, None. Both become None at the same step (m + n + 1). Now a is b (both are None), the loop stops, and we return None. Correct answer, no special case.

The teacher's tip: don't assume a clever trick like this is hard to think of. Relate the problem to a real-life picture (a fair race) and the different approaches appear naturally: either shorten the longer track, or make both run the same combined track.

5Approach steps

1. Set a = headA, b = headB.
2. While a and b are different nodes:
3. — if a is None, restart it at headB; otherwise move a = a.next.
4. — if b is None, restart it at headA; otherwise move b = b.next.
5. When the loop stops, a and b are the same: the joining node, or both None. Return a.

6Code (Python)

class Solution:
    def getIntersectionNode(self, headA, headB):
        a, b = headA, headB
        while a is not b:
            if a is None:
                a = headB        # finished track A, now run track B
            else:
                a = a.next
            if b is None:
                b = headA        # finished track B, now run track A
            else:
                b = b.next
        return a

The teacher then shortens the two if/else blocks with the ternary operator ("condition ? this : that" in Java). Python's version is x if condition else y:

class Solution:
    def getIntersectionNode(self, headA, headB):
        a, b = headA, headB
        while a is not b:
            a = headB if a is None else a.next
            b = headA if b is None else b.next
        return a

7Code line by line

8Dry run

Same lists as Part A: x = 2 (a1, a2), y = 4 (b1..b4), z = 3 (c1, c2, c3). The formula says they meet after x + z + 1 + y = 2 + 3 + 1 + 4 = 10 steps.

Snapshot at step 6 (after a switched):

headA →             [4] → [1] ─┐
                               ├→ [8] → [4] → [5] → None
headB → [5] → [6] → [1] → [2] ─┘               ↑
         ↑                                     b
         a   (a has run 5 nodes + None, now on B)

Snapshot at step 10:

headA →             [4] → [1] ─┐
                               ├→ [8] → [4] → [5] → None
headB → [5] → [6] → [1] → [2] ─┘   ↑
                                  a, b    (both walked 10 steps)

Step 6 is a nice reminder: value 5 under both pointers, yet not the answer. Only is (same node) is correct.

A no-intersection dry run

A = 1 → 2 → 3, B = 7 → 8 (no shared node). m = 3, n = 2.

At step 6 = m + n + 1, both are None → loop ends → return None.

9Complexity & remember

• Time O(m + n): each runner walks at most its own list and then the other one. That is about 2n when the lengths are similar, compared with about 3n in Part A (worst case m + n + max(m, n), or 2m + n when m is the larger).
• Space O(1): two pointers, nothing else.

Part C · Revision page

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

def build(vals):
    head = None
    for v in reversed(vals):
        head = ListNode(v, head)
    return head

def tail_of(head):
    while head.next:
        head = head.next
    return head

shared = build([8, 4, 5])
A = build([4, 1]);       tail_of(A).next = shared
B = build([5, 6, 1, 2]); tail_of(B).next = shared

s = Solution()
print(s.getIntersectionNode(A, B) is shared)              # True
print(s.getIntersectionNode(build([1, 2, 3]), build([7, 8])))  # None

Based on this video: Intersection of Two Linked Lists