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.

Practice

1. What does the term intersection point of two linked lists mean?

easy

A. The first node of the longer linked list.

B. The node where both linked lists share the same reference (memory address).

C. The node where the values of both linked lists are equal.

D. The last node of the shorter linked list.

Solution

1. Step 1: Understand linked list nodes

   Each node in a linked list has a value and a reference (memory address) to the next node.

2. Step 2: Define intersection point

   The intersection point is where two linked lists share the exact same node reference, not just the same value.

3. Final Answer:

   The node where both linked lists share the same reference (memory address). -> Option B

4. Quick Check:

   Intersection means shared node reference [OK]

Hint: Intersection means same node object, not just same value [OK]

Common Mistakes:

• Confusing same value with same node reference
• Thinking intersection is based on node values
• Assuming intersection is always at the start

2. Which of the following Python code snippets correctly initializes two linked lists headA and headB that intersect at node with value 8?

easy

A. headA = Node(3)
headB = Node(99)
headA.next = Node(8)
headB.next = Node(8)

B. node = Node(8)
headA = Node(3, node)
headB = Node(99, node)

C. headA = Node(3)
headB = Node(99)
node = Node(8)
headA.next = node
headB.next = node

D. nodeA = Node(3)
nodeB = Node(99)
nodeC = Node(8)
headA = nodeA
headB = nodeB

Solution

1. Step 1: Understand intersection setup

   To create intersection, both lists must share the same node object for the intersecting node.

2. Step 2: Check code correctness

   headA = Node(3) headB = Node(99) node = Node(8) headA.next = node headB.next = node creates node with value 8 once and assigns it as next for both lists, ensuring intersection.

3. Final Answer:

   headA and headB share the same node object for value 8. -> Option C

4. Quick Check:

   Shared node object creates intersection [OK]

Hint: Intersection needs shared node object, not just same value nodes [OK]

Common Mistakes:

• Creating separate nodes with same value instead of shared node
• Assigning next pointers incorrectly
• Not linking nodes properly

3. What will be the output of the following Python code that finds the intersection point of two linked lists?

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

def get_intersection(headA, headB):
    a, b = headA, headB
    while a != b:
        a = a.next if a else headB
        b = b.next if b else headA
    return a.val if a else None

# Setup
common = Node(7)
common.next = Node(10)
headA = Node(3)
headA.next = Node(6)
headA.next.next = common
headB = Node(99)
headB.next = common

print(get_intersection(headA, headB))

medium

A. 7

B. 10

C. None

D. 3

Solution

1. Step 1: Understand the intersection nodes

   Both lists share node with value 7 and then 10. Intersection is at node with value 7.

2. Step 2: Trace the get_intersection function

   Pointers a and b traverse lists; when they meet at node 7, function returns 7.

3. Final Answer:

   7 -> Option A

4. Quick Check:

   First shared node value is 7 [OK]

Hint: Two-pointer method returns first shared node value [OK]

Common Mistakes:

• Returning value of second shared node
• Returning None if not careful with pointer resets
• Confusing node values with references

4. The following code attempts to find the intersection point of two linked lists but does not work correctly. What is the main error?

def get_intersection(headA, headB):
    a, b = headA, headB
    while a != b:
        a = a.next
        b = b.next
    return a.val if a else None

medium

A. It returns the value of the last node instead of the intersection.

B. It compares node values instead of node references.

C. It uses incorrect variable names for nodes.

D. It does not reset pointers to the other list when reaching the end.

Solution

1. Step 1: Analyze pointer movement

   The code moves pointers a and b forward but never resets them to the other list's head.

2. Step 2: Understand consequence

   Without resetting, pointers may reach None at different times and never meet, missing intersection.

3. Final Answer:

   It does not reset pointers to the other list when reaching the end. -> Option D

4. Quick Check:

   Resetting pointers is key for intersection detection [OK]

Hint: Reset pointers to other list head when reaching end [OK]

Common Mistakes:

• Not resetting pointers causes infinite loop or no detection
• Comparing values instead of references
• Returning wrong node value

5. Given two singly linked lists that may or may not intersect, which approach correctly finds the intersection point in O(m+n) time and O(1) space?

Options:
A) Use two pointers starting at heads; move each pointer to the other list's head when reaching end until they meet.
B) Use a hash set to store nodes of first list, then check nodes of second list for membership.
C) Compare every node of first list with every node of second list.
D) Reverse both lists and compare nodes from the start until mismatch.

hard

A. Two-pointer switching heads method until pointers meet.

B. Hash set membership check for intersection.

C. Nested loops comparing all nodes pairwise.

D. Reverse lists and compare nodes from start.

Solution

1. Step 1: Analyze time and space complexity

   Two-pointer switching heads method until pointers meet. uses two pointers and no extra space, running in O(m+n) time and O(1) space.

2. Step 2: Compare other options

   Hash set membership check for intersection. uses extra space (hash set), Nested loops comparing all nodes pairwise. is O(m*n), Reverse lists and compare nodes from start. modifies lists and is inefficient.

3. Final Answer:

   Two-pointer switching heads method until pointers meet. -> Option A

4. Quick Check:

   Two-pointer method is optimal for intersection [OK]

Hint: Two-pointer switch method finds intersection efficiently [OK]

Common Mistakes:

• Using extra space unnecessarily
• Using nested loops causing slow performance
• Modifying lists destructively