Intersection of Two Linked Lists

📋

Problem

Imagine two train tracks merging into one at some point. You want to find the exact point where the two tracks join.

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null. The linked lists must retain their original structure after the function returns.

The number of nodes of listA is in the range [1, 10^5].The number of nodes of listB is in the range [1, 10^5].1 <= Node.val <= 10^5If the two linked lists have no intersection at all, return null.

Edge cases: One or both lists are empty → return nullIntersection at the head node → return head nodeLists of different lengths intersecting → return intersection node

</>

IDE

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:public ListNode getIntersectionNode(ListNode headA, ListNode headB)ListNode* getIntersectionNode(ListNode* headA, ListNode* headB)function getIntersectionNode(headA, headB)

def getIntersectionNode(headA, headB):
    # Write your solution here
    pass

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    // Write your solution here
    return nullptr;
}

function getIntersectionNode(headA, headB) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Node with same value but different referenceComparing node values instead of node references for intersection.✅ Compare nodes using 'is' in Python or reference equality in other languages.

Wrong: Null when intersection existsNot handling intersection at head or skipping early checks for head equality.✅ Add early check if headA is headB and return head immediately.

Wrong: Wrong intersection node or null due to greedy value matchingMatching nodes by value instead of reference, causing false negatives or positives.✅ Use two-pointer technique to compare node references after length equalization.

Wrong: Timeout on large inputsUsing brute force nested loops O(m*n) approach.✅ Implement two-pointer length equalization approach with O(m+n) time complexity.

Wrong: Missed intersection due to off-by-one pointer switchingIncorrect pointer switching logic causing pointers to miss intersection node.✅ Switch pointers to other list head only after reaching null, not before.

✓

Test Cases

Try testing your code on empty and single-node lists to catch base cases.

Consider tricky cases where values repeat but nodes differ, and pointer switching logic.

Optimize your solution to linear time using two-pointer technique to handle large inputs.

t1_01basic

Input{"headA":[4,1,8,4,5],"headB":[5,6,1,8,4,5],"intersectVal":8,"skipA":2,"skipB":3}

Expected8

⏱ Performance - must finish in 2000ms

The two lists intersect at node with value 8, which is the same node object in memory.

💡 Think about how to detect the same node object, not just equal values.

💡 Use two pointers traversing each list and switch heads when reaching the end.

💡 When pointers meet, that node is the intersection or null if none.

Why it failed: Returned wrong node or value because you compared node values instead of node references. Fix by comparing nodes with 'is' (Python) or '==' for references.

✓ Correctly identified the intersection node by reference.

t1_02basic

Input{"headA":[1,9,1,2,4],"headB":[3,2,4],"intersectVal":2,"skipA":3,"skipB":1}

Expected2

⏱ Performance - must finish in 2000ms

Lists intersect at node with value 2 after skipping 3 nodes in listA and 1 node in listB.

💡 Align the pointers by switching heads after reaching list ends.

💡 Check if pointers are equal by reference, not just value.

💡 Return the node where pointers meet or null if none.

Why it failed: Incorrect intersection detection due to comparing node values instead of references. Fix by comparing node references directly.

✓ Correctly found intersection node using two-pointer technique.

t2_01edge

Input{"headA":[],"headB":[]}

Expectednull

⏱ Performance - must finish in 2000ms

Both lists are empty, so no intersection exists.

💡 Check if either list head is null before processing.

💡 If one or both lists are empty, return null immediately.

💡 Handle empty input as a base case.

Why it failed: Code crashes or returns non-null when input lists are empty. Fix by adding null checks for empty lists at start.

✓ Correctly returns null for empty input lists.

t2_02edge

Input{"headA":[1],"headB":[1]}

Expectednull

⏱ Performance - must finish in 2000ms

Single node lists with same value but different nodes do not intersect.

💡 Intersection means same node object, not just equal values.

💡 Check node references, not values.

💡 Return null if no node reference matches.

Why it failed: Returned intersection due to comparing node values instead of references. Fix by comparing node references.

✓ Correctly returns null when single nodes differ by reference.

t2_03edge

Input{"headA":[7,2,1],"headB":[7,2,1],"intersectVal":7,"skipA":0,"skipB":0}

Expected7

⏱ Performance - must finish in 2000ms

Lists intersect at head node (value 7), meaning both heads are the same node.

💡 Check if headA and headB are the same node at start.

💡 If heads are equal by reference, return head immediately.

💡 This is a base case for intersection at head.

Why it failed: Missed intersection at head node by not checking head equality first. Fix by adding early check if headA is headB.

✓ Correctly detects intersection at head node.

t3_01corner

Input{"headA":[1,2,3,4,5,6,7,8,9,10],"headB":[11,12,13,14,15,6,7,8,9,10],"intersectVal":6,"skipA":5,"skipB":5}

Expected6

⏱ Performance - must finish in 2000ms

Lists of different lengths intersect at node with value 6 after skipping 5 nodes in each list.

💡 Greedy approach of matching values fails here due to duplicates.

💡 Use two-pointer technique to equalize lengths and find intersection by reference.

💡 Switch pointers to other list head when reaching end to align traversal.

Why it failed: Greedy value matching returns wrong node or null. Fix by comparing node references and using two-pointer length equalization.

✓ Correctly finds intersection despite different lengths and duplicate values.

t3_02corner

Input{"headA":[1,2,3,4,5],"headB":[6,7,8,9,10]}

Expectednull

⏱ Performance - must finish in 2000ms

Lists have no intersection but some values may be similar or different.

💡 Do not confuse equal values with intersection.

💡 Check node references, not values.

💡 Return null if no node reference matches after full traversal.

Why it failed: Incorrectly returns intersection due to value equality. Fix by comparing node references only.

✓ Correctly returns null when no intersection exists.

t3_03corner

Input{"headA":[1,2,3,4,5],"headB":[3,4,5],"intersectVal":3,"skipA":2,"skipB":0}

Expected3

⏱ Performance - must finish in 2000ms

Intersection occurs at node with value 3 which is not head of either list.

💡 Beware of off-by-one errors in pointer switching.

💡 Ensure pointers switch lists exactly once when reaching end.

💡 Return node where pointers meet by reference.

Why it failed: Off-by-one error causes missing intersection node. Fix pointer switching logic to switch heads only after reaching null.

✓ Correctly identifies intersection node with proper pointer switching.

t4_01performance

Input{"headA":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"headB":[101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200],"intersectVal":null,"skipA":100,"skipB":100}

Expectednull

⏱ Performance - must finish in 2000ms

Two large lists of length 100 with no intersection; solution must run in O(m+n) time within 2 seconds.

💡 Brute force O(m*n) will time out on large inputs.

💡 Use two-pointer length equalization technique for O(m+n) time.

💡 Avoid nested loops; switch pointers between lists to align traversal.

Why it failed: Solution times out due to O(m*n) brute force complexity. Fix by implementing two-pointer length equalization approach with O(m+n) time.

✓ Solution runs efficiently in O(m+n) time on large inputs.

Practice

1. 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

2. Examine the following buggy code for adding two numbers represented by linked lists in-place. Identify the line that causes the bug where the final carry digit is lost when both lists are exhausted.

medium

A. Line with loop condition missing carry: while l1 or l2:

B. Line with carry update: carry = total // 10

C. Line with condition: while l1 or l2:

D. Line with prev update: prev = l1

Solution

1. Step 1: Identify loop condition

   The loop runs only while l1 or l2 is not None, ignoring carry after both lists end.

2. Step 2: Understand consequence

   If carry remains after both lists are exhausted, it is never processed, losing the last digit.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Loop must include carry to handle final digit [OK]

Hint: Loop must run while carry exists to avoid losing last digit [OK]

Common Mistakes:

• Forgetting carry in loop condition
• Misplacing carry update inside loop
• Incorrectly updating prev pointer

3. What is the time complexity of deleting a node in a singly linked list given only access to that node (no head pointer), using the optimal in-place approach that copies the next node's data and deletes the next node?

medium

A. O(n), because you need to traverse the list to find the node

B. O(1), because the operation only involves copying data and pointer updates

C. O(n), because you must recursively copy data from subsequent nodes

D. O(log n), because the deletion involves dividing the list

Solution

1. Step 1: Identify operations performed

   The algorithm copies the next node's value into the current node and updates the next pointer to skip the next node.

2. Step 2: Analyze time complexity

   These operations are constant time, no traversal or recursion is needed.

3. Step 3: Consider the initial access to the node

   However, if only the node to delete is given, no traversal is needed. But if only the value is given and node must be found, traversal is needed.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Copy and pointer update are O(1) operations [OK]

Hint: No traversal needed; only local pointer updates [OK]

Common Mistakes:

• Assuming traversal from head is needed, making it O(n)
• Confusing recursion with iterative approach
• Thinking deletion involves multiple node copies

4. Consider the following buggy code snippet for removing the nth node from the end of a linked list. Which line contains the subtle bug that causes incorrect behavior when removing the head node?

medium

A. Line 13: Wrong condition for node removal

B. Line 10: Incorrect base case for recursion

C. Line 5: Missing dummy node initialization

D. Line 15: Returning head instead of dummy.next

Solution

1. Step 1: Identify missing dummy node

   Without a dummy node, removing the head node causes pointer errors or incorrect list head.

2. Step 2: Check recursion call and return

   Recursion is called on head, but no dummy means no safe predecessor to update head pointer.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Dummy node is essential to handle head removal safely [OK]

Hint: Always use dummy node to handle head removal [OK]

Common Mistakes:

• Not using dummy node
• Incorrect recursion base case
• Returning wrong node after removal

5. Suppose you want to extend the reverse sublist problem to allow multiple disjoint sublists to be reversed in one pass (e.g., reverse positions [2,3] and [5,6] simultaneously). Which of the following approaches correctly adapts the algorithm without breaking list integrity or increasing time complexity beyond O(n)?

hard

A. Modify the recursive approach to track multiple successor pointers and reverse all sublists in a single traversal.

B. Extract all sublists, reverse them independently, then rebuild the entire list by stitching reversed and untouched parts.

C. Run the recursive reverseBetween function separately for each sublist, updating the head each time.

D. Use a greedy approach to swap node values between all specified sublists without changing pointers.

Solution

1. Step 1: Analyze naive multiple calls approach

   Running reverseBetween separately for each sublist can break list integrity because each call assumes original list structure, causing pointer conflicts.

2. Step 2: Consider single traversal with multiple successor tracking

   Modifying recursion to handle multiple sublists and track successors allows reversing all sublists in one pass, preserving list integrity and O(n) time.

3. Step 3: Evaluate other options

   Extracting and rebuilding is O(n) but more complex and error-prone; greedy swapping node values does not reverse nodes and breaks problem constraints.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Single traversal with multiple successor pointers is optimal and correct [OK]

Hint: Multiple sublists require single traversal with careful pointer tracking [OK]

Common Mistakes:

• Running separate reversals breaks list links
• Assuming value swaps suffice for reversal
• Rebuilding entire list is inefficient