Intersection of Two Linked Lists

▶

Steps

setup

Initialize pointers pA and pB at heads of listA and listB

Set pA to the head of listA (node with value 4) and pB to the head of listB (node with value 5). This prepares for simultaneous traversal.

💡 Starting both pointers at the heads allows us to traverse both lists in parallel.

Line:

pA, pB = headA, headB

💡 Both pointers start at the beginning of their respective lists.

traverse

Advance pA and pB to next nodes

Move pA from node 4 to node 1, and pB from node 5 to node 6, continuing traversal in their lists.

💡 Advancing pointers stepwise shows how they progress through their lists.

Line:

pA = pA.next if pA else headB
pB = pB.next if pB else headA

💡 Both pointers move forward one node in their respective lists.

traverse

Advance pA and pB to next nodes

Move pA from node 1 to node 8 (intersection candidate), and pB from node 6 to node 1.

💡 Pointers continue moving forward, approaching the intersection node.

Line:

pA = pA.next if pA else headB
pB = pB.next if pB else headA

💡 pA reaches the intersection node earlier than pB.

traverse

Advance pA and pB to next nodes

Move pA from node 8 to node 4, and pB from node 1 to node 8 (intersection candidate).

💡 Pointers continue moving forward, pB now reaches the intersection node.

Line:

pA = pA.next if pA else headB
pB = pB.next if pB else headA

💡 pB catches up to the intersection node after pA.

traverse

Advance pA and pB to next nodes

Move pA from node 4 to node 5, and pB from node 8 to node 4.

💡 Pointers continue moving forward, pA nearing the end of listA.

Line:

pA = pA.next if pA else headB
pB = pB.next if pB else headA

💡 pA is at the last node of listA, pB is still traversing the intersection segment.

traverse

Advance pA and pB; pA reaches end and switches to headB

pA moves from node 5 to null (end of listA), then switches to head of listB (node 6). pB moves from node 4 to node 5.

💡 Pointer pA switches lists to equalize traversal length; pB continues forward.

Line:

pA = pA.next if pA else headB
pB = pB.next if pB else headA

💡 Switching heads allows pointers to traverse the other list, balancing length difference.

traverse

Advance pA and pB

pA moves from node 6 to node 7, pB moves from node 5 to null (end of listB).

💡 pB reaches end and will switch to headA next step; pA continues in listB.

Line:

pA = pA.next if pA else headB
pB = pB.next if pB else headA

💡 Both pointers will traverse the other list to align their paths.

traverse

pB switches to headA; pA advances

pB switches from null to headA (node 4), pA moves from node 7 to node 8.

💡 Switching heads again ensures both pointers traverse both lists fully.

Line:

pA = pA.next if pA else headB
pB = pB.next if pB else headA

💡 Pointers now aligned to traverse the other list, equalizing path lengths.

traverse

Advance pA and pB

pA moves from node 8 to node 4, pB moves from node 4 to node 1.

💡 Pointers are now traversing the other lists and approaching the intersection node simultaneously.

Line:

pA = pA.next if pA else headB
pB = pB.next if pB else headA

💡 Both pointers are now on the shared tail segment of the lists.

traverse

Advance pA and pB

pA moves from node 4 to node 5, pB moves from node 1 to node 8 (intersection node).

💡 Pointers continue traversing the shared tail segment, getting closer to meeting.

Line:

pA = pA.next if pA else headB
pB = pB.next if pB else headA

💡 Pointers are synchronized on the shared nodes now.

traverse

Advance pA and pB; pA reaches end and switches to headB

pA moves from node 5 to null (end of listB), pB moves from node 8 to node 4.

💡 pA reaches end and will switch to headB next; pB moves forward in shared tail.

Line:

pA = pA.next if pA else headB
pB = pB.next if pB else headA

💡 Pointers continue traversing both lists fully to align.

traverse

pA switches to headB; pB advances

pA switches from null to headB (node 6), pB moves from node 4 to node 5.

💡 Both pointers have traversed both lists once and are about to start second traversal.

Line:

pA = pA.next if pA else headB
pB = pB.next if pB else headA

💡 Pointers are synchronized to meet at intersection or null.

traverse

Advance pA and pB

pA moves from node 6 to node 7, pB moves from node 5 to null (end of listB).

💡 pB reaches end and will switch to headA next; pA continues in listB.

Line:

pA = pA.next if pA else headB
pB = pB.next if pB else headA

💡 Pointers will meet at intersection node if it exists.

traverse

pB switches to headA; pA advances to intersection node

pB switches from null to headA (node 4), pA moves from node 7 to node 8. Both pointers now point to the same node.

💡 Pointers meet at the intersection node, confirming the intersection.

Line:

pA = pA.next if pA else headB
pB = pB.next if pB else headA

💡 Pointers meeting means intersection node found.

reconstruct

Return the intersection node

Since pA and pB point to the same node, return this node as the intersection.

💡 Returning the node confirms the intersection found by the pointers.

Line:

return pA

💡 The algorithm terminates with the correct intersection node.

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

def getIntersectionNode(headA, headB):
    if not headA or not headB:
        return None  # STEP 1
    pA, pB = headA, headB  # STEP 1
    while pA is not pB:  # STEP 2-14 loop
        pA = pA.next if pA else headB  # STEP 2-14 advance or switch
        pB = pB.next if pB else headA  # STEP 2-14 advance or switch
    return pA  # STEP 15

if __name__ == '__main__':
    intersect = ListNode(8, ListNode(4, ListNode(5)))
    listA = ListNode(4, ListNode(1, intersect))
    listB = ListNode(5, ListNode(6, ListNode(1, intersect)))
    result = getIntersectionNode(listA, listB)
    print(result.val if result else 'No intersection')

📊

Intersection of Two Linked Lists - Watch the Algorithm Execute, Step by Step

Watching the pointers move and switch lists helps you understand how length differences are equalized without extra space.

advance

4

→

1

→

8

→

4

→

5

→

5

→

6

→

1

advance

4

→

1

→

8

→

4

→

5

→

5

→

6

→

1

advance

4

→

1

→

8

→

4

→

5

→

5

→

6

→

1

advance

4

→

1

→

8

→

4

→

5

→

5

→

6

→

1

advance

4

→

1

→

8

→

4

→

5

→

5

→

6

→

1

advance

4

→

1

→

8

→

4

→

5

→

5

→

6

→

1

advance

4

→

1

→

8

→

4

→

5

→

5

→

6

→

1

advance

4

→

1

→

8

→

4

→

5

→

5

→

6

→

1

advance

4

→

1

→

8

→

4

→

5

→

5

→

6

→

1

advance

4

→

1

→

8

→

4

→

5

→

5

→

6

→

1

advance

4

→

1

→

8

→

4

→

5

→

5

→

6

→

1

advance

4

→

1

→

8

→

4

→

5

→

5

→

6

→

1

advance

4

→

1

→

8

→

4

→

5

→

5

→

6

→

1

compare

4

→

1

→

8

→

4

→

5

→

5

→

6

→

1

Result: 3

return

4

→

1

→

8

→

4

→

5

→

5

→

6

→

1

Result: 3

Key Takeaways

✓ Pointer switching equalizes the difference in list lengths without extra space.

This insight is hard to see from code alone because the pointer switching logic is subtle and non-intuitive without visualization.

✓ Pointers meet at the intersection node only if the lists intersect; otherwise, both become null simultaneously.

Visualizing the pointers moving and switching lists clarifies how the algorithm detects intersection or absence thereof.

✓ The algorithm traverses each list at most twice, ensuring O(n) time complexity.

Seeing the pointers traverse both lists fully helps understand the efficiency and correctness of the approach.

Practice

1. You are given k sorted linked lists and need to merge them into one sorted linked list efficiently. Which approach guarantees the optimal time complexity for this problem?

easy

A. Merge all lists into one array, then sort the array and rebuild the linked list.

B. Use dynamic programming to store intermediate merged results and avoid repeated merges.

C. Use a min-heap (priority queue) to repeatedly extract the smallest node among the heads of the lists.

D. Merge the lists one by one sequentially, merging two lists at a time from left to right.

Solution

1. Step 1: Understand problem constraints

   We have k sorted linked lists and want to merge them efficiently.

2. Step 2: Compare approaches

   Brute force sorting all nodes is O(N log N). Sequential merges cost O(kN). Min-heap approach extracts smallest node in O(log k) time, total O(N log k), which is optimal.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Min-heap approach uses priority queue to achieve O(N log k) [OK]

Hint: Min-heap merges k lists in O(N log k) time [OK]

Common Mistakes:

• Thinking sequential merges are optimal
• Assuming sorting all nodes is best
• Confusing DP with merge approach

2. Consider the following Python code implementing the recursive two-pointer palindrome check for a linked list. Given the linked list 1 -> 2 -> 2 -> 1, what is the final return value of the function isPalindrome?

easy

A. False

B. Raises an exception

C. True

D. None

Solution

1. Step 1: Trace recursion to the end of the list

   The recursion reaches the last node (value 1), then unwinds comparing front and current nodes.

2. Step 2: Compare front and current nodes on unwind

   Comparisons: front=1 vs current=1 (match), front moves to 2; front=2 vs current=2 (match), front moves to 2; front=2 vs current=2 (match), front moves to 1; front=1 vs current=1 (match). All match, so returns True.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   All node pairs match, so palindrome check returns True [OK]

Hint: Recursive check compares front and back nodes symmetrically [OK]

Common Mistakes:

• Confusing return value with None
• Off-by-one in recursion causing False
• Assuming exception on empty or single node

3. Given the following Python code implementing the recursive reversal of a sublist, what is the output when reversing positions 2 to 3 of the list [1, 2, 3, 4]?

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

successor = None

def reverseN(head, n):
    global successor
    if n == 1:
        successor = head.next
        return head
    last = reverseN(head.next, n - 1)
    head.next.next = head
    head.next = successor
    return last

def reverseBetween(head, left, right):
    if left == 1:
        return reverseN(head, right)
    head.next = reverseBetween(head.next, left - 1, right - 1)
    return head

# Build list
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(3):
    nodes[i].next = nodes[i+1]

new_head = reverseBetween(nodes[0], 2, 3)
curr = new_head
while curr:
    print(curr.val, end=' ')
    curr = curr.next

easy

A. 1 3 2 4

B. 1 2 3 4

C. 3 2 1 4

D. 1 4 3 2

Solution

1. Step 1: Trace reverseN for n=2 starting at node with val=2

   reverseN reverses first 2 nodes starting at node 2: it recursively reverses node 3, then sets pointers to reverse links between 2 and 3.

2. Step 2: Reconnect reversed sublist to original list

   Node 1 points to reversed sublist head (node 3), and the tail of reversed sublist (node 2) points to node 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected partial reversal between positions 2 and 3 [OK]

Hint: Partial reversal swaps nodes 2 and 3 only [OK]

Common Mistakes:

• Assuming full list reversed
• Off-by-one error reversing wrong nodes
• Confusing node values with positions

4. Given the following recursive code for swapping nodes in pairs, what is the output when the input list is 1 -> 2 -> 3 -> null?

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

def swapPairs(head: ListNode) -> ListNode:
    def helper(node):
        if not node or not node.next:
            return node
        first = node
        second = node.next
        first.next = helper(second.next)
        second.next = first
        return second
    return helper(head)

# Input list: 1 -> 2 -> 3 -> null

What is the printed output after swapping pairs?

easy

A. 2 3 1

B. 1 3 2

C. 2 1 3

D. 3 2 1

Solution

1. Step 1: Trace helper on node with val=1

   First = 1, Second = 2; recursively call helper on node with val=3.

2. Step 2: Trace helper on node with val=3

   Node 3 has no next, so return node 3 as is.

3. Step 3: Complete first call

   Set first.next = node 3, second.next = first (1), return second (2). Resulting list: 2 -> 1 -> 3.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Output matches expected swapped pairs [OK]

Hint: Recursive swaps pairs, last odd node remains [OK]

Common Mistakes:

• Swapping values instead of nodes
• Misplacing last node in odd-length list

5. The following code attempts to merge k sorted linked lists using a min-heap. Identify the line that contains a subtle bug that can cause incorrect merging or runtime errors.

medium

A. Line: current.next = smallest

B. Line: Missing 'current = current.next' after attaching smallest

C. Line: while heap:

D. Line: if node: heapq.heappush(heap, node)

Solution

1. Step 1: Review pointer updates in loop

   After attaching smallest to current.next, current must move forward.

2. Step 2: Identify missing line

   Code lacks 'current = current.next', so current stays, causing incorrect list linking.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without advancing current, merged list nodes overwrite each other [OK]

Hint: Always advance current pointer after attaching a node [OK]

Common Mistakes:

• Forgetting to move current pointer
• Misplacing heap push conditions
• Confusing heap pop with list traversal