Intersection of Two Linked Lists

🎯

Intersection of Two Linked Lists

easyLINKED_LISTAmazonFacebookMicrosoft

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

💡 This problem asks to find the node where two singly linked lists intersect. Beginners often struggle because linked lists don't have indices, so you can't just compare positions directly. Understanding pointer manipulation and traversal is key.

📋

Problem Statement

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.

💡

Example

Input"listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]"

OutputReference to node with value 8

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

Input"listA = [1,9,1,2,4], listB = [3,2,4]"

OutputReference to node with value 2

The intersection starts at node with value 2.

Input"listA = [2,6,4], listB = [1,5]"

Outputnull

The two lists do not intersect.

• One or both lists are empty → return null
• Intersection at the head node → return head node
• Lists of different lengths intersecting → return intersection node
• Lists with no intersection but similar values → return null

⚠️

Common Mistakes

Comparing node values instead of node references

Returns incorrect intersection node or false positives

✅ Compare nodes by reference (identity), not by value

Not handling empty lists properly

Code may crash or return wrong result

✅ Check if either head is null before processing

Infinite loop in two pointer approach if not careful

Code runs forever without returning

✅ Ensure pointers switch lists only once and loop condition is correct

Modifying the input lists accidentally

Alters input data structure, causing unexpected behavior

✅ Do not change next pointers or list structure; only traverse

Using extra space unnecessarily when asked for O(1) space

Fails interview or loses points

✅ Use two pointer approach to achieve O(1) space

🧠

Brute Force (Nested Loops)

💡 This approach is the most straightforward and helps understand the problem deeply by checking every possible pair of nodes. It is inefficient but builds intuition.

Intuition

For each node in list A, check every node in list B to see if they are the same node (by reference). If yes, return that node.

Algorithm

1. Traverse each node in list A.
2. For each node in list A, traverse each node in list B.
3. Compare nodes by reference to check if they are the same.
4. Return the node if found; otherwise, return null after all checks.

💡 Nested loops are easy to understand but inefficient because they repeat many comparisons.

</>

Code

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

def getIntersectionNode(headA, headB):
    currentA = headA
    while currentA:
        currentB = headB
        while currentB:
            if currentA is currentB:
                return currentA
            currentB = currentB.next
        currentA = currentA.next
    return None

# Example usage:
if __name__ == '__main__':
    # Create intersecting lists for testing
    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')

Line Notes

def getIntersectionNode(headA, headB):Defines the function to find intersection node

while currentA:Outer loop iterates over each node in list A

while currentB:Inner loop iterates over each node in list B for each node in A

if currentA is currentB:Checks if nodes are the exact same object (intersection)

return currentAReturns the intersecting node immediately when found

return NoneReturns None if no intersection is found after full traversal

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode currentA = headA;
        while (currentA != null) {
            ListNode currentB = headB;
            while (currentB != null) {
                if (currentA == currentB) {
                    return currentA;
                }
                currentB = currentB.next;
            }
            currentA = currentA.next;
        }
        return null;
    }

    public static void main(String[] args) {
        ListNode intersect = new ListNode(8);
        intersect.next = new ListNode(4);
        intersect.next.next = new ListNode(5);
        ListNode listA = new ListNode(4);
        listA.next = new ListNode(1);
        listA.next.next = intersect;
        ListNode listB = new ListNode(5);
        listB.next = new ListNode(6);
        listB.next.next = new ListNode(1);
        listB.next.next.next = intersect;

        Solution sol = new Solution();
        ListNode result = sol.getIntersectionNode(listA, listB);
        System.out.println(result != null ? result.val : "No intersection");
    }
}

Line Notes

public ListNode getIntersectionNode(ListNode headA, ListNode headB)Method signature for intersection detection

while (currentA != null)Outer loop traverses list A nodes

while (currentB != null)Inner loop traverses list B nodes for each node in A

if (currentA == currentB)Checks if nodes are the same object reference

return currentA;Returns the intersecting node immediately

return null;Returns null if no intersection found

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *currentA = headA;
        while (currentA != nullptr) {
            ListNode *currentB = headB;
            while (currentB != nullptr) {
                if (currentA == currentB) {
                    return currentA;
                }
                currentB = currentB->next;
            }
            currentA = currentA->next;
        }
        return nullptr;
    }
};

int main() {
    ListNode *intersect = new ListNode(8);
    intersect->next = new ListNode(4);
    intersect->next->next = new ListNode(5);
    ListNode *listA = new ListNode(4);
    listA->next = new ListNode(1);
    listA->next->next = intersect;
    ListNode *listB = new ListNode(5);
    listB->next = new ListNode(6);
    listB->next->next = new ListNode(1);
    listB->next->next->next = intersect;

    Solution sol;
    ListNode *result = sol.getIntersectionNode(listA, listB);
    if (result) cout << result->val << endl;
    else cout << "No intersection" << endl;
    return 0;
}

Line Notes

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)Function to find intersection node

while (currentA != nullptr)Outer loop iterates over list A

while (currentB != nullptr)Inner loop iterates over list B for each node in A

if (currentA == currentB)Checks if nodes are the same memory address

return currentA;Returns intersection node immediately

return nullptr;Returns nullptr if no intersection found

function ListNode(val) {
    this.val = val;
    this.next = null;
}

function getIntersectionNode(headA, headB) {
    let currentA = headA;
    while (currentA !== null) {
        let currentB = headB;
        while (currentB !== null) {
            if (currentA === currentB) {
                return currentA;
            }
            currentB = currentB.next;
        }
        currentA = currentA.next;
    }
    return null;
}

// Example usage:
const intersect = new ListNode(8);
intersect.next = new ListNode(4);
intersect.next.next = new ListNode(5);
const listA = new ListNode(4);
listA.next = new ListNode(1);
listA.next.next = intersect;
const listB = new ListNode(5);
listB.next = new ListNode(6);
listB.next.next = new ListNode(1);
listB.next.next.next = intersect;

console.log(getIntersectionNode(listA, listB)?.val || 'No intersection');

Line Notes

function getIntersectionNode(headA, headB)Defines function to find intersection

while (currentA !== null)Outer loop traverses list A

while (currentB !== null)Inner loop traverses list B for each node in A

if (currentA === currentB)Checks if nodes are the same object reference

return currentA;Returns intersection node immediately

return null;Returns null if no intersection found

⏱

Complexity

TimeO(m*n)

SpaceO(1)

For each node in list A (m nodes), we traverse all nodes in list B (n nodes), resulting in O(m*n) time.

💡 If both lists have 1000 nodes, this approach does up to 1,000,000 comparisons, which is very slow.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large lists but is useful to understand the problem and correctness before optimizing.

🧠

Hash Set to Store Visited Nodes

💡 This approach uses extra memory to speed up the search by remembering nodes visited in one list and checking the other against them.

Intuition

Traverse list A and store each node in a hash set. Then traverse list B and check if any node is in the set. The first such node is the intersection.

Algorithm

1. Traverse list A and add each node to a hash set.
2. Traverse list B and check if any node is in the hash set.
3. Return the first node found in the set as the intersection.
4. If no node is found, return null.

💡 Using a hash set avoids repeated comparisons by remembering nodes already seen.

</>

Code

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

def getIntersectionNode(headA, headB):
    visited = set()
    currentA = headA
    while currentA:
        visited.add(currentA)
        currentA = currentA.next
    currentB = headB
    while currentB:
        if currentB in visited:
            return currentB
        currentB = currentB.next
    return None

# Example usage:
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')

Line Notes

visited = set()Creates a set to store visited nodes from list A

visited.add(currentA)Adds current node of list A to the set

if currentB in visited:Checks if current node of list B is in the set

return currentBReturns the intersecting node immediately

return NoneReturns None if no intersection found

import java.util.HashSet;

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> visited = new HashSet<>();
        ListNode currentA = headA;
        while (currentA != null) {
            visited.add(currentA);
            currentA = currentA.next;
        }
        ListNode currentB = headB;
        while (currentB != null) {
            if (visited.contains(currentB)) {
                return currentB;
            }
            currentB = currentB.next;
        }
        return null;
    }

    public static void main(String[] args) {
        ListNode intersect = new ListNode(8);
        intersect.next = new ListNode(4);
        intersect.next.next = new ListNode(5);
        ListNode listA = new ListNode(4);
        listA.next = new ListNode(1);
        listA.next.next = intersect;
        ListNode listB = new ListNode(5);
        listB.next = new ListNode(6);
        listB.next.next = new ListNode(1);
        listB.next.next.next = intersect;

        Solution sol = new Solution();
        ListNode result = sol.getIntersectionNode(listA, listB);
        System.out.println(result != null ? result.val : "No intersection");
    }
}

Line Notes

HashSet<ListNode> visited = new HashSet<>();Creates a hash set to store nodes from list A

visited.add(currentA);Adds current node of list A to the set

if (visited.contains(currentB))Checks if current node of list B is in the set

return currentB;Returns the intersecting node immediately

return null;Returns null if no intersection found

#include <iostream>
#include <unordered_set>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> visited;
        ListNode *currentA = headA;
        while (currentA != nullptr) {
            visited.insert(currentA);
            currentA = currentA->next;
        }
        ListNode *currentB = headB;
        while (currentB != nullptr) {
            if (visited.find(currentB) != visited.end()) {
                return currentB;
            }
            currentB = currentB->next;
        }
        return nullptr;
    }
};

int main() {
    ListNode *intersect = new ListNode(8);
    intersect->next = new ListNode(4);
    intersect->next->next = new ListNode(5);
    ListNode *listA = new ListNode(4);
    listA->next = new ListNode(1);
    listA->next->next = intersect;
    ListNode *listB = new ListNode(5);
    listB->next = new ListNode(6);
    listB->next->next = new ListNode(1);
    listB->next->next->next = intersect;

    Solution sol;
    ListNode *result = sol.getIntersectionNode(listA, listB);
    if (result) cout << result->val << endl;
    else cout << "No intersection" << endl;
    return 0;
}

Line Notes

unordered_set<ListNode*> visited;Creates a hash set to store pointers to nodes from list A

visited.insert(currentA);Inserts current node pointer from list A into the set

if (visited.find(currentB) != visited.end())Checks if current node pointer from list B is in the set

return currentB;Returns the intersecting node immediately

return nullptr;Returns nullptr if no intersection found

function ListNode(val) {
    this.val = val;
    this.next = null;
}

function getIntersectionNode(headA, headB) {
    const visited = new Set();
    let currentA = headA;
    while (currentA !== null) {
        visited.add(currentA);
        currentA = currentA.next;
    }
    let currentB = headB;
    while (currentB !== null) {
        if (visited.has(currentB)) {
            return currentB;
        }
        currentB = currentB.next;
    }
    return null;
}

// Example usage:
const intersect = new ListNode(8);
intersect.next = new ListNode(4);
intersect.next.next = new ListNode(5);
const listA = new ListNode(4);
listA.next = new ListNode(1);
listA.next.next = intersect;
const listB = new ListNode(5);
listB.next = new ListNode(6);
listB.next.next = new ListNode(1);
listB.next.next.next = intersect;

console.log(getIntersectionNode(listA, listB)?.val || 'No intersection');

Line Notes

const visited = new Set();Creates a set to store visited nodes from list A

visited.add(currentA);Adds current node from list A to the set

if (visited.has(currentB))Checks if current node from list B is in the set

return currentB;Returns the intersecting node immediately

return null;Returns null if no intersection found

⏱

Complexity

TimeO(m + n)

SpaceO(m)

We traverse list A once to build the set, then list B once to check membership, so O(m+n) time. Space is O(m) for the set.

💡 For lists of length 1000, this does about 2000 operations and stores 1000 nodes in memory.

Interview Verdict: Accepted but uses extra space

This approach is efficient time-wise but uses extra memory, which might not be allowed in some interviews.

🧠

Two Pointer Length Equalization (Optimal)

💡 This approach uses two pointers and clever traversal to find the intersection without extra space and in linear time. It is the most optimal and commonly expected solution.

Intuition

Advance two pointers through the lists. When one pointer reaches the end, redirect it to the head of the other list. Eventually, they align at the intersection or both reach null.

Algorithm

1. Initialize two pointers, pA and pB, at the heads of list A and B.
2. Traverse each list with the pointers; when a pointer reaches the end, redirect it to the head of the other list.
3. Continue until the pointers meet at the intersection node or both become null.
4. Return the intersection node or null if no intersection.

💡 Redirecting pointers equalizes path lengths, ensuring they meet at the intersection or end simultaneously.

</>

Code

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
    pA, pB = headA, headB
    while pA is not pB:
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA
    return pA

# Example usage:
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')

Line Notes

if not headA or not headB:Handles edge case where one or both lists are empty

pA, pB = headA, headBInitialize two pointers at the heads of the lists

while pA is not pB:Loop until pointers meet or both become None

pA = pA.next if pA else headBMove pointer A forward or redirect to headB if at end

pB = pB.next if pB else headAMove pointer B forward or redirect to headA if at end

return pAReturn intersection node or None if no intersection

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }
        return pA;
    }

    public static void main(String[] args) {
        ListNode intersect = new ListNode(8);
        intersect.next = new ListNode(4);
        intersect.next.next = new ListNode(5);
        ListNode listA = new ListNode(4);
        listA.next = new ListNode(1);
        listA.next.next = intersect;
        ListNode listB = new ListNode(5);
        listB.next = new ListNode(6);
        listB.next.next = new ListNode(1);
        listB.next.next.next = intersect;

        Solution sol = new Solution();
        ListNode result = sol.getIntersectionNode(listA, listB);
        System.out.println(result != null ? result.val : "No intersection");
    }
}

Line Notes

if (headA == null || headB == null) return null;Handles empty list edge cases

ListNode pA = headA, pB = headB;Initialize two pointers at list heads

while (pA != pB)Loop until pointers meet or both null

pA = (pA == null) ? headB : pA.next;Redirect pointer A to headB after reaching end

pB = (pB == null) ? headA : pB.next;Redirect pointer B to headA after reaching end

return pA;Return intersection node or null

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return nullptr;
        ListNode *pA = headA, *pB = headB;
        while (pA != pB) {
            pA = pA ? pA->next : headB;
            pB = pB ? pB->next : headA;
        }
        return pA;
    }
};

int main() {
    ListNode *intersect = new ListNode(8);
    intersect->next = new ListNode(4);
    intersect->next->next = new ListNode(5);
    ListNode *listA = new ListNode(4);
    listA->next = new ListNode(1);
    listA->next->next = intersect;
    ListNode *listB = new ListNode(5);
    listB->next = new ListNode(6);
    listB->next->next = new ListNode(1);
    listB->next->next->next = intersect;

    Solution sol;
    ListNode *result = sol.getIntersectionNode(listA, listB);
    if (result) cout << result->val << endl;
    else cout << "No intersection" << endl;
    return 0;
}

Line Notes

if (!headA || !headB) return nullptr;Handles empty list edge cases

ListNode *pA = headA, *pB = headB;Initialize two pointers at list heads

while (pA != pB)Loop until pointers meet or both null

pA = pA ? pA->next : headB;Redirect pointer A to headB after reaching end

pB = pB ? pB->next : headA;Redirect pointer B to headA after reaching end

return pA;Return intersection node or nullptr

function ListNode(val) {
    this.val = val;
    this.next = null;
}

function getIntersectionNode(headA, headB) {
    if (!headA || !headB) return null;
    let pA = headA, pB = headB;
    while (pA !== pB) {
        pA = pA ? pA.next : headB;
        pB = pB ? pB.next : headA;
    }
    return pA;
}

// Example usage:
const intersect = new ListNode(8);
intersect.next = new ListNode(4);
intersect.next.next = new ListNode(5);
const listA = new ListNode(4);
listA.next = new ListNode(1);
listA.next.next = intersect;
const listB = new ListNode(5);
listB.next = new ListNode(6);
listB.next.next = new ListNode(1);
listB.next.next.next = intersect;

console.log(getIntersectionNode(listA, listB)?.val || 'No intersection');

Line Notes

if (!headA || !headB) return null;Handles empty list edge cases

let pA = headA, pB = headB;Initialize two pointers at list heads

while (pA !== pB)Loop until pointers meet or both null

pA = pA ? pA.next : headB;Redirect pointer A to headB after reaching end

pB = pB ? pB.next : headA;Redirect pointer B to headA after reaching end

return pA;Return intersection node or null

⏱

Complexity

TimeO(m + n)

SpaceO(1)

Each pointer traverses each list at most twice, so total time is linear in combined length. No extra space is used.

💡 For lists of length 1000, this does about 2000 pointer moves and uses constant memory.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews due to its efficiency and elegance.

📊

All Approaches - One-Glance Tradeoffs

💡 The two pointer approach is the best to code in interviews due to its optimal time and space. Hash set is a good intermediate step. Brute force is mainly for understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(m*n)	O(1)	No	N/A	Mention only - never code
2. Hash Set	O(m + n)	O(m)	No	N/A	Good to mention, but clarify space trade-off
3. Two Pointer Length Equalization	O(m + n)	O(1)	No	N/A	Code this approach in 95% of interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply and practice all approaches. Start with brute force to build intuition, then progress to optimal solutions. Practice explaining your thought process clearly.

How to Present

Clarify the problem and ask about constraints.Describe the brute force approach and its inefficiency.Explain the hash set approach and trade-offs.Present the two pointer optimal approach with intuition.Write clean code and test with examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of linked lists, pointer manipulation, and ability to optimize from brute force to optimal. They also check for edge case handling and clean code.

Common Follow-ups

• What if the lists are cyclic? → Use cycle detection and then intersection logic.
• Can you solve without extra space? → Yes, use two pointer length equalization.

💡 Follow-ups often test your knowledge of cycles in linked lists and space optimization techniques.

🔍

Pattern Recognition

When to Use

1) Two linked lists given, 2) Need to find intersection node, 3) Intersection means same node object, 4) No modification allowed

Signature Phrases

'return the node at which the two lists intersect''if the two linked lists have no intersection, return null'

NOT This Pattern When

Problems asking to merge lists or find values rather than node references

Similar Problems

Linked List Cycle II - uses similar pointer tricks to find cycle startFind the Duplicate Number - uses cycle detection analogyMerge Two Sorted Lists - also involves linked list pointer manipulation

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 optimal merge K sorted lists approach using a min-heap. Given the input lists: [1->4->5], [1->3->4], [2->6], what is the value of current.next.val after the third iteration of the while loop?

easy

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Initialize heap with heads: 1,1,2

   Heap order: [1,1,2]

2. Step 2: Iterations of while loop

   1st pop: smallest=1 (from first list), push 4; 2nd pop: smallest=1 (from second list), push 3; 3rd pop: smallest=2 (from third list), push 6. After 3rd iteration, current.next.val = 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Third extracted node value is 2 [OK]

Hint: Track heap pops and pushed next nodes carefully [OK]

Common Mistakes:

• Off-by-one iteration counting
• Confusing which node is popped
• Forgetting to push next nodes

3. What is the time complexity of the optimal min-heap based algorithm for merging k sorted linked lists with a total of N nodes?

medium

A. O(N k) because each node is compared with nodes from all k lists.

B. O(N log N) because all nodes are pushed and popped from the heap.

C. O(kN) because each list is merged sequentially with all others.

D. O(N log k) because each of the N nodes is pushed and popped from a heap of size at most k.

Solution

1. Step 1: Identify heap operations per node

   Each node is pushed and popped exactly once from a heap of size ≤ k.

2. Step 2: Calculate complexity

   Heap push/pop cost is O(log k), total O(N log k) for N nodes.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Heap size depends on k, not N, so O(N log k) [OK]

Hint: Heap size is k, not N, so complexity is O(N log k) [OK]

Common Mistakes:

• Confusing N and k in log factor
• Assuming heap size grows with N
• Thinking sequential merges are optimal

4. The following code attempts to reverse nodes in k-groups but contains a subtle bug. Which line causes the bug that leads to incorrect list connections after reversal?

medium

A. Line: prev = reverseLinkedList(group_prev.next, k)

B. Line: tail.next = group_prev.next # Bug here

C. Line: if count < k: break

D. Line: group_prev = dummy

Solution

1. Step 1: Understand the role of tail.next after reversal

   After reversing k nodes, tail (original head) should point to group_next to maintain list continuity.

2. Step 2: Identify the incorrect pointer assignment

   Assigning tail.next = group_prev.next reconnects tail to the old head, causing cycles or broken links.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct line should be tail.next = group_next [OK]

Hint: Tail must connect to next group's head, not old head [OK]

Common Mistakes:

• Forgetting to update tail.next to group_next
• Misassigning pointers causing cycles

5. The following code attempts to rotate a linked list to the right by k places. Identify the line that contains a subtle bug that can cause the list to become cyclic or truncated incorrectly.

medium

A. Line: tail.next = head # make circular

B. Line: slow.next = slow # BUG: incorrect break causing cycle

C. Line: for _ in range(k): fast = fast.next

D. Line: k = k % length

Solution

1. Step 1: Understand the purpose of breaking the list

   After rotation, the list must be broken at the new tail by setting slow.next = None.

2. Step 2: Identify the bug

   The original code sets slow.next = slow, which creates a cycle instead of breaking the list.

3. Step 3: Correct fix

   Change to slow.next = None to properly break the list.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Correct break is slow.next = None [OK]

Hint: Break list by setting slow.next = None [OK]

Common Mistakes:

• Setting slow.next to itself or wrong node causing cycles
• Not handling k modulo length correctly
• Forgetting to make list circular before rotation