Intersection Point of Two Linked Lists in DSA Python

Mental Model

Two linked lists may share some nodes at the end, forming an intersection. We want to find the first shared node.

Analogy: Imagine two roads that start separately but merge into one road later. The intersection point is where the two roads join and continue together.

List A: 1 -> 2 -> 3 -> 7 -> 8 -> null
List B: 4 -> 5 -> 7 -> 8 -> null
                 ↑
          intersection point

Dry Run Walkthrough

Input: List A: 1->2->3->7->8, List B: 4->5->7->8

Goal: Find the node where both lists start to share nodes (value 7 in this example).

Step 1: Calculate lengths of both lists: lenA=5, lenB=4

List A: 1 -> 2 -> 3 -> 7 -> 8 -> null
List B: 4 -> 5 -> 7 -> 8 -> null

Why: Knowing lengths helps align the lists to compare nodes at the same distance from the end.

Step 2: Advance pointer in longer list (A) by difference (1 step)

List A pointer at node 2 -> 3 -> 7 -> 8 -> null
List B pointer at node 4 -> 5 -> 7 -> 8 -> null

Why: Align both pointers so they have equal nodes remaining to traverse.

Step 3: Compare nodes at pointers: 2 vs 4 (different), move both forward

List A pointer at 3 -> 7 -> 8 -> null
List B pointer at 5 -> 7 -> 8 -> null

Why: Nodes differ, so move forward to find intersection.

Step 4: Compare nodes: 3 vs 5 (different), move both forward

List A pointer at 7 -> 8 -> null
List B pointer at 7 -> 8 -> null

Why: Still different, continue moving forward.

Step 5: Compare nodes: 7 vs 7 (same node), intersection found

Intersection node: 7 -> 8 -> null

Why: Pointers meet at the same node, this is the intersection point.

Result:

7 -> 8 -> null is the intersection point

Annotated Code

DSA Python

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

def get_length(head):
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    return length

def get_intersection_node(headA, headB):
    lenA = get_length(headA)  # get length of list A
    lenB = get_length(headB)  # get length of list B

    # Align start pointers
    currA, currB = headA, headB
    if lenA > lenB:
        for _ in range(lenA - lenB):
            currA = currA.next  # advance longer list pointer
    else:
        for _ in range(lenB - lenA):
            currB = currB.next  # advance longer list pointer

    # Move both pointers until they meet or reach end
    while currA and currB:
        if currA == currB:
            return currA  # intersection found
        currA = currA.next  # move forward
        currB = currB.next  # move forward
    return None  # no intersection

# Driver code to create lists and test
# Shared part
shared = ListNode(7, ListNode(8))

# List A: 1->2->3->7->8
headA = ListNode(1, ListNode(2, ListNode(3, shared)))
# List B: 4->5->7->8
headB = ListNode(4, ListNode(5, shared))

intersection = get_intersection_node(headA, headB)
if intersection:
    # Print from intersection to end
    curr = intersection
    result = []
    while curr:
        result.append(str(curr.val))
        curr = curr.next
    print(" -> ".join(result) + " -> null")
else:
    print("No intersection")

lenA = get_length(headA) # get length of list A

calculate length of first list

lenB = get_length(headB) # get length of list B

calculate length of second list

if lenA > lenB: for _ in range(lenA - lenB): currA = currA.next # advance longer list pointer

advance pointer in longer list to align both lists

else: for _ in range(lenB - lenA): currB = currB.next # advance longer list pointer

advance pointer in longer list to align both lists

while currA and currB: if currA == currB: return currA # intersection found currA = currA.next # move forward currB = currB.next # move forward

move both pointers forward until intersection or end

Output

7 -> 8 -> null

Complexity Analysis

Time: O(m + n) because we traverse both lists to get lengths and then traverse aligned parts once

Space: O(1) because we use only a few pointers and counters, no extra data structures

vs Alternative: Naive approach compares every node of one list with every node of the other, O(m*n), which is slower

Edge Cases

One or both lists are empty

Function returns None immediately, no intersection

DSA Python

while currA and currB:

Lists do not intersect at all

Function returns None after traversing both lists

DSA Python

while currA and currB:

Intersection at head node (both lists are same)

Function returns head node as intersection

DSA Python

if currA == currB:
            return currA

When to Use This Pattern

When you see two linked lists and need to find if they share nodes, use the intersection point pattern by aligning lengths and moving pointers together.

Common Mistakes

Mistake: Comparing node values instead of node references to find intersection
Fix: Compare node objects (references), not just their values

Mistake: Not aligning the longer list pointer before simultaneous traversal
Fix: Calculate lengths and advance the longer list pointer by the difference first

Summary

Finds the first shared node where two linked lists intersect.

Use when two linked lists may merge and you want to find the merge point.

Align the lists by length, then move pointers together to find the intersection.