Bird
Raised Fist0
Interview Prepfast-slow-pointersmediumAmazonMicrosoftFacebook

Reorder List (L0→Ln→L1→Ln-1)

Choose your preparation mode4 modes available
🎯
Reorder List (L0→Ln→L1→Ln-1)
mediumTWO_POINTERAmazonMicrosoftFacebook

Imagine you have a playlist of songs and want to reorder it so that the first song is followed by the last, then the second, then the second last, and so on, creating a new listening experience.

💡 This problem involves manipulating linked lists by rearranging nodes in a specific pattern. Beginners often struggle because it requires multiple linked list operations combined: finding the middle, reversing a list, and merging two lists. Understanding each step separately helps build confidence.
📋
Problem Statement

Given the head of a singly linked list, reorder the list to follow the pattern: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ... You must do this in-place without altering the node values, only rearranging the nodes themselves.

The number of nodes in the list is in the range [1, 10^5]Node values can be any integerYou must reorder the list in-place with O(1) extra space
💡
Example
Input"head = [1,2,3,4]"
Output[1,4,2,3]

The list is reordered by taking first node 1, last node 4, second node 2, then third node 3.

Input"head = [1,2,3,4,5]"
Output[1,5,2,4,3]

After reordering, nodes alternate from start and end moving inward.

  • Single node list → output same list
  • Two node list → output same list
  • List with all nodes having same value → reorder still applies
  • Very long list (e.g., 10^5 nodes) → must be efficient and in-place
⚠️
Common Mistakes
Not terminating the reordered list with null

Leads to cycles or infinite loops when traversing

✅ Always set the next pointer of the last node to null after reordering

Incorrectly merging nodes causing lost references

Nodes get skipped or list structure breaks

✅ Use temporary pointers to store next nodes before re-linking

Not handling edge cases like single or two node lists

Code may crash or reorder unnecessarily

✅ Add base case checks for lists with less than 3 nodes

Using extra space when problem requires in-place

Fails interview constraints or inefficient for large inputs

✅ Use fast-slow pointer and reverse/merge technique to reorder in-place

Misusing fast and slow pointers causing infinite loops

Code hangs or crashes

✅ Ensure fast pointer moves two steps and slow moves one step carefully with null checks

🧠
Brute Force (Using Extra Array to Store Nodes)
💡 This approach exists to build intuition by explicitly storing nodes in an array to reorder them. It is straightforward but uses extra space, which is not optimal but helps understand the problem.

Intuition

Store all nodes in an array, then reorder by alternating from the front and back indices, reconnecting nodes accordingly.

Algorithm

  1. Traverse the linked list and store all nodes in an array.
  2. Use two pointers, one at the start and one at the end of the array.
  3. Alternately connect nodes from the start and end pointers moving inward.
  4. Set the next pointer of the last node to null to terminate the list.
💡 The main challenge is to carefully reconnect nodes without losing references, which is easier when nodes are indexed in an array.
</>
Code
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorderList(head):
    if not head or not head.next:
        return
    nodes = []
    curr = head
    while curr:
        nodes.append(curr)
        curr = curr.next
    i, j = 0, len(nodes) - 1
    while i < j:
        nodes[i].next = nodes[j]
        i += 1
        if i == j:
            break
        nodes[j].next = nodes[i]
        j -= 1
    nodes[i].next = None

# Driver code to test
if __name__ == '__main__':
    # Create linked list 1->2->3->4
    n4 = ListNode(4)
    n3 = ListNode(3, n4)
    n2 = ListNode(2, n3)
    n1 = ListNode(1, n2)
    reorderList(n1)
    # Print reordered list
    curr = n1
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()
Line Notes
nodes = []Initialize array to store nodes for indexed access
while curr:Traverse entire list to collect nodes
nodes[i].next = nodes[j]Link node from front to node from back
nodes[i].next = NoneTerminate reordered list to avoid cycles
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        List<ListNode> nodes = new ArrayList<>();
        ListNode curr = head;
        while (curr != null) {
            nodes.add(curr);
            curr = curr.next;
        }
        int i = 0, j = nodes.size() - 1;
        while (i < j) {
            nodes.get(i).next = nodes.get(j);
            i++;
            if (i == j) break;
            nodes.get(j).next = nodes.get(i);
            j--;
        }
        nodes.get(i).next = null;
    }

    public static void main(String[] args) {
        ListNode n4 = new ListNode(4);
        ListNode n3 = new ListNode(3); n3.next = n4;
        ListNode n2 = new ListNode(2); n2.next = n3;
        ListNode n1 = new ListNode(1); n1.next = n2;
        new Solution().reorderList(n1);
        ListNode curr = n1;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}
Line Notes
List<ListNode> nodes = new ArrayList<>();Store nodes for random access by index
while (curr != null)Traverse list to fill array
nodes.get(i).next = nodes.get(j);Connect front node to back node
nodes.get(i).next = null;End list properly to prevent cycles
#include <iostream>
#include <vector>
using namespace std;

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

void reorderList(ListNode* head) {
    if (!head || !head->next) return;
    vector<ListNode*> nodes;
    ListNode* curr = head;
    while (curr) {
        nodes.push_back(curr);
        curr = curr->next;
    }
    int i = 0, j = nodes.size() - 1;
    while (i < j) {
        nodes[i]->next = nodes[j];
        i++;
        if (i == j) break;
        nodes[j]->next = nodes[i];
        j--;
    }
    nodes[i]->next = nullptr;
}

int main() {
    ListNode* n4 = new ListNode(4);
    ListNode* n3 = new ListNode(3); n3->next = n4;
    ListNode* n2 = new ListNode(2); n2->next = n3;
    ListNode* n1 = new ListNode(1); n1->next = n2;
    reorderList(n1);
    ListNode* curr = n1;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}
Line Notes
vector<ListNode*> nodes;Use vector to store pointers to nodes for indexed access
while (curr) { nodes.push_back(curr); curr = curr->next; }Collect all nodes in order
nodes[i]->next = nodes[j];Link front node to back node
nodes[i]->next = nullptr;Terminate list to avoid cycles
function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function reorderList(head) {
    if (!head || !head.next) return;
    const nodes = [];
    let curr = head;
    while (curr) {
        nodes.push(curr);
        curr = curr.next;
    }
    let i = 0, j = nodes.length - 1;
    while (i < j) {
        nodes[i].next = nodes[j];
        i++;
        if (i === j) break;
        nodes[j].next = nodes[i];
        j--;
    }
    nodes[i].next = null;
}

// Test
const n4 = new ListNode(4);
const n3 = new ListNode(3, n4);
const n2 = new ListNode(2, n3);
const n1 = new ListNode(1, n2);
reorderList(n1);
let curr = n1;
while (curr) {
    console.log(curr.val);
    curr = curr.next;
}
Line Notes
const nodes = [];Array to hold nodes for indexed access
while (curr) { nodes.push(curr); curr = curr.next; }Traverse list to collect nodes
nodes[i].next = nodes[j];Connect front node to back node
nodes[i].next = null;Terminate list to prevent cycles
⏱
Complexity
TimeO(n)
SpaceO(n)

We traverse the list once to store nodes, then reorder in O(n). Extra space is used to store all nodes.

💡 For n=10, this means about 20 operations plus storing 10 nodes in an array.
Interview Verdict: Accepted but not optimal due to extra space

This approach works but uses extra memory, which is not ideal for large inputs or in-place constraints.

🧠
Better (Find Middle, Reverse Second Half, Merge)
💡 This approach improves space by doing all operations in-place. It uses the fast-slow pointer technique to find the middle, reverses the second half, then merges two halves. It is a classic linked list manipulation pattern.

Intuition

Split the list into two halves at the middle, reverse the second half, then merge nodes alternately from the first and reversed second half.

Algorithm

  1. Use fast and slow pointers to find the middle of the list.
  2. Reverse the second half of the list starting from the middle.
  3. Merge the first half and reversed second half by alternating nodes.
  4. Ensure the last node points to null to terminate the list.
💡 Each step is a common linked list operation; combining them carefully achieves the reorder without extra space.
</>
Code
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorderList(head):
    if not head or not head.next:
        return
    # Find middle
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    # Reverse second half
    prev, curr = None, slow.next
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    slow.next = None
    # Merge two halves
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2

# Driver code to test
if __name__ == '__main__':
    n5 = ListNode(5)
    n4 = ListNode(4, n5)
    n3 = ListNode(3, n4)
    n2 = ListNode(2, n3)
    n1 = ListNode(1, n2)
    reorderList(n1)
    curr = n1
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()
Line Notes
slow, fast = head, headInitialize pointers to find middle
while fast.next and fast.next.next:Move fast twice as fast as slow to find middle
curr.next = prevReverse pointer direction to reverse second half
first.next = secondMerge nodes from first and second halves alternately
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode prev = null, curr = slow.next;
        slow.next = null;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        ListNode first = head, second = prev;
        while (second != null) {
            ListNode tmp1 = first.next, tmp2 = second.next;
            first.next = second;
            second.next = tmp1;
            first = tmp1;
            second = tmp2;
        }
    }

    public static void main(String[] args) {
        ListNode n5 = new ListNode(5);
        ListNode n4 = new ListNode(4); n4.next = n5;
        ListNode n3 = new ListNode(3); n3.next = n4;
        ListNode n2 = new ListNode(2); n2.next = n3;
        ListNode n1 = new ListNode(1); n1.next = n2;
        new Solution().reorderList(n1);
        ListNode curr = n1;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}
Line Notes
ListNode slow = head, fast = head;Initialize pointers to find middle node
while (fast.next != null && fast.next.next != null)Move fast pointer twice as fast as slow
curr.next = prev;Reverse second half by changing next pointers
first.next = second;Merge nodes from first and reversed second half
#include <iostream>
using namespace std;

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

void reorderList(ListNode* head) {
    if (!head || !head->next) return;
    ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* prev = nullptr;
    ListNode* curr = slow->next;
    slow->next = nullptr;
    while (curr) {
        ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    ListNode* first = head;
    ListNode* second = prev;
    while (second) {
        ListNode* tmp1 = first->next;
        ListNode* tmp2 = second->next;
        first->next = second;
        second->next = tmp1;
        first = tmp1;
        second = tmp2;
    }
}

int main() {
    ListNode* n5 = new ListNode(5);
    ListNode* n4 = new ListNode(4); n4->next = n5;
    ListNode* n3 = new ListNode(3); n3->next = n4;
    ListNode* n2 = new ListNode(2); n2->next = n3;
    ListNode* n1 = new ListNode(1); n1->next = n2;
    reorderList(n1);
    ListNode* curr = n1;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}
Line Notes
ListNode *slow = head, *fast = head;Initialize pointers to find middle
while (fast->next && fast->next->next)Move fast pointer twice as fast as slow
curr->next = prev;Reverse second half by pointer reversal
first->next = second;Merge nodes from first and reversed second half
function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function reorderList(head) {
    if (!head || !head.next) return;
    let slow = head, fast = head;
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    let prev = null, curr = slow.next;
    slow.next = null;
    while (curr) {
        let nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    let first = head, second = prev;
    while (second) {
        let tmp1 = first.next;
        let tmp2 = second.next;
        first.next = second;
        second.next = tmp1;
        first = tmp1;
        second = tmp2;
    }
}

// Test
const n5 = new ListNode(5);
const n4 = new ListNode(4, n5);
const n3 = new ListNode(3, n4);
const n2 = new ListNode(2, n3);
const n1 = new ListNode(1, n2);
reorderList(n1);
let curr = n1;
while (curr) {
    console.log(curr.val);
    curr = curr.next;
}
Line Notes
let slow = head, fast = head;Initialize pointers to find middle node
while (fast.next && fast.next.next)Move fast pointer twice as fast as slow
curr.next = prev;Reverse second half by changing next pointers
first.next = second;Merge nodes from first and reversed second half
⏱
Complexity
TimeO(n)
SpaceO(1)

Each step (finding middle, reversing, merging) is O(n) and done in-place, so total O(n) time and constant extra space.

💡 For n=10, this means about 30 operations but no extra memory allocation besides pointers.
Interview Verdict: Accepted and optimal for in-place reorder

This is the preferred approach in interviews because it meets the in-place constraint and is efficient.

🧠
Alternative: Recursive Reordering (Not Recommended for Large Lists)
💡 This approach uses recursion to reorder nodes by pairing front and back nodes. It is elegant but risks stack overflow on large inputs and is less intuitive.

Intuition

Use recursion to reach the end of the list, then reorder nodes on the way back by pairing front and back nodes.

Algorithm

  1. Use a helper recursive function with a front pointer passed by reference.
  2. Traverse to the end of the list recursively.
  3. On returning, reorder nodes by connecting front and back nodes alternately.
  4. Stop recursion when pointers meet or cross to avoid cycles.
💡 The recursion stack simulates two pointers moving inward, but managing pointers carefully is tricky.
</>
Code
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorderList(head):
    def helper(right):
        nonlocal left, stop
        if not right:
            return
        helper(right.next)
        if stop:
            return
        if left == right or left.next == right:
            right.next = None
            stop = True
            return
        tmp = left.next
        left.next = right
        right.next = tmp
        left = tmp

    left = head
    stop = False
    helper(head)

# Driver code
if __name__ == '__main__':
    n5 = ListNode(5)
    n4 = ListNode(4, n5)
    n3 = ListNode(3, n4)
    n2 = ListNode(2, n3)
    n1 = ListNode(1, n2)
    reorderList(n1)
    curr = n1
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()
Line Notes
def helper(right):Recursive function to traverse to end
if not right: returnBase case for recursion
if left == right or left.next == right:Stop condition when pointers meet or cross
left.next = rightReorder nodes by linking front to back
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    private ListNode left;
    private boolean stop;

    public void reorderList(ListNode head) {
        left = head;
        stop = false;
        helper(head);
    }

    private void helper(ListNode right) {
        if (right == null) return;
        helper(right.next);
        if (stop) return;
        if (left == right || left.next == right) {
            right.next = null;
            stop = true;
            return;
        }
        ListNode tmp = left.next;
        left.next = right;
        right.next = tmp;
        left = tmp;
    }

    public static void main(String[] args) {
        ListNode n5 = new ListNode(5);
        ListNode n4 = new ListNode(4); n4.next = n5;
        ListNode n3 = new ListNode(3); n3.next = n4;
        ListNode n2 = new ListNode(2); n2.next = n3;
        ListNode n1 = new ListNode(1); n1.next = n2;
        new Solution().reorderList(n1);
        ListNode curr = n1;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}
Line Notes
private ListNode left;Pointer to front node updated during recursion
if (right == null) return;Base case for recursion
if (left == right || left.next == right)Stop condition when pointers meet or cross
left.next = right;Link front node to back node during unwind
#include <iostream>
using namespace std;

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

class Solution {
    ListNode* left;
    bool stop;
public:
    void reorderList(ListNode* head) {
        left = head;
        stop = false;
        helper(head);
    }
private:
    void helper(ListNode* right) {
        if (!right) return;
        helper(right->next);
        if (stop) return;
        if (left == right || (left && left->next == right)) {
            right->next = nullptr;
            stop = true;
            return;
        }
        ListNode* tmp = left->next;
        left->next = right;
        right->next = tmp;
        left = tmp;
    }
};

int main() {
    ListNode* n5 = new ListNode(5);
    ListNode* n4 = new ListNode(4); n4->next = n5;
    ListNode* n3 = new ListNode(3); n3->next = n4;
    ListNode* n2 = new ListNode(2); n2->next = n3;
    ListNode* n1 = new ListNode(1); n1->next = n2;
    Solution sol;
    sol.reorderList(n1);
    ListNode* curr = n1;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}
Line Notes
ListNode* left;Pointer to front node updated during recursion
if (!right) return;Base case for recursion
if (left == right || (left && left->next == right))Stop condition when pointers meet or cross
left->next = right;Link front node to back node during recursion unwind
function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function reorderList(head) {
    let left = head;
    let stop = false;
    function helper(right) {
        if (!right) return;
        helper(right.next);
        if (stop) return;
        if (left === right || left.next === right) {
            right.next = null;
            stop = true;
            return;
        }
        let tmp = left.next;
        left.next = right;
        right.next = tmp;
        left = tmp;
    }
    helper(head);
}

// Test
const n5 = new ListNode(5);
const n4 = new ListNode(4, n5);
const n3 = new ListNode(3, n4);
const n2 = new ListNode(2, n3);
const n1 = new ListNode(1, n2);
reorderList(n1);
let curr = n1;
while (curr) {
    console.log(curr.val);
    curr = curr.next;
}
Line Notes
let left = head;Pointer to front node updated during recursion
if (!right) return;Base case for recursion
if (left === right || left.next === right)Stop condition when pointers meet or cross
left.next = right;Link front node to back node during recursion unwind
⏱
Complexity
TimeO(n)
SpaceO(n) due to recursion stack

Recursion depth is O(n), so space is linear. Time is linear as each node is visited once.

💡 For n=10, this means 10 recursive calls on the stack, which can cause stack overflow for large n.
Interview Verdict: Accepted but not recommended for large inputs

While elegant, recursion risks stack overflow and is less practical than the iterative approach.

📊
All Approaches - One-Glance Tradeoffs
💡 In 95% of interviews, code the Better approach using fast-slow pointers, reverse, and merge. Mention brute force to show understanding, and avoid recursion for large inputs.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(n)O(n)NoYesMention only - never code due to extra space
2. Better (Fast-Slow + Reverse + Merge)O(n)O(1)NoYesCode this approach for optimal solution
3. Recursive ReorderingO(n)O(n) due to recursion stackYesYesMention if asked, avoid coding for large inputs
💼
Interview Strategy
💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding. Progress to the optimal approach emphasizing in-place operations. Practice coding and testing thoroughly.

How to Present

Clarify the problem and constraints with the interviewer.Describe the brute force approach using extra space to reorder nodes.Explain the optimal approach using fast and slow pointers, reversing, and merging.Discuss edge cases and test your code with examples.Mention alternative recursive approach if time permits.

Time Allocation

Clarify: 2min → Approach discussion: 5min → Code optimal approach: 10min → Test & debug: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of linked list manipulation, pointer handling, and ability to optimize space. They also check if you can handle edge cases and write clean, bug-free code.

Common Follow-ups

  • What if the list is doubly linked? → You can reorder similarly but have to update prev pointers.
  • Can you do this with recursion? → Yes, but watch for stack overflow on large lists.
💡 These follow-ups test your adaptability and deeper understanding of linked list variants and recursion tradeoffs.
🔍
Pattern Recognition

When to Use

1) Problem involves linked list reordering or rearrangement, 2) Pattern requires pairing nodes from front and back, 3) Constraints require in-place solution, 4) Fast and slow pointers can find middle.

Signature Phrases

reorder listin-place rearrangementfast and slow pointersmerge two halves

NOT This Pattern When

Problems that only require traversal or simple insertion/deletion without reordering or pairing nodes from front and back.

Similar Problems

Palindrome Linked List - also uses fast and slow pointers to find middle and reverseMerge Two Sorted Lists - merging two lists alternatelyReverse Linked List - reversing a sublist or entire list

Practice

(1/5)
1. Consider the following code snippet implementing the optimal approach to copy a list with random pointers. Given the input list: 1 -> 2 -> 3, where node 1's random points to node 3, node 2's random points to node 1, and node 3's random is null, what is the value of copy_curr.random.val after the last iteration of the separation step (Step 3)?
easy
A. 1
B. 3
C. None (random pointer is null)
D. 2

Solution

  1. Step 1: Trace Step 1 (Interleaving nodes)

    Original list: 1->2->3. After interleaving: 1->1'->2->2'->3->3'.
  2. Step 2: Trace Step 2 (Assign random pointers)

    Node 1's random points to 3, so 1'.random = 3'. Node 2's random points to 1, so 2'.random = 1'. Node 3's random is null, so 3'.random = null.
  3. Step 3: Trace Step 3 (Separate lists)

    After separation, copy_curr starts at 1'. After last iteration, copy_curr is at 3'. Its random pointer is null, so copy_curr.random.val does not exist.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    copy_curr.random is null after last iteration [OK]
Hint: Random pointers point to copied nodes via original's next [OK]
Common Mistakes:
  • Confusing original and copied nodes during separation
  • Off-by-one error in advancing copy_curr
  • Assuming random pointers remain unchanged
2. You need to implement a data structure that supports the following operations efficiently: get element by index, add element at head, add element at tail, add element at an arbitrary index, and delete element at an arbitrary index. Which approach best guarantees efficient average-case performance for all these operations?
easy
A. Use a dynamic array and resize it when needed to support all operations.
B. Use a balanced binary search tree keyed by index to support all operations in O(log n).
C. Use a singly linked list with sentinel head and tail pointers, maintaining the size for boundary checks.
D. Use a hash map to store index-to-node mappings for constant time access.

Solution

  1. Step 1: Understand operation requirements

    The problem requires efficient get, add at head, add at tail, add at index, and delete at index operations.
  2. Step 2: Evaluate approaches

    Dynamic arrays have O(n) add/delete at head or arbitrary index due to shifting. Singly linked lists have O(1) add at head/tail but O(n) get and add/delete at arbitrary index. Balanced BSTs keyed by index can support all operations in O(log n) time, providing efficient average-case performance. Hash maps do not maintain order and cannot efficiently support index-based operations.
  3. Step 3: Choose best approach

    Balanced BST keyed by index offers O(log n) for all operations, which is more efficient on average than linked list or array for arbitrary index operations.
  4. Final Answer:

    Option B -> Option B
  5. Quick Check:

    Balanced BST supports all required operations efficiently [OK]
Hint: Balanced BST keyed by index supports all operations in O(log n) [OK]
Common Mistakes:
  • Assuming linked list provides efficient arbitrary index access
  • Thinking arrays support O(1) insertions at head
  • Assuming hash maps maintain order
3. Given the following code snippet implementing the in-place iterative flattening of a multilevel doubly linked list, and the input list: 1 <-> 2 <-> 3, where node 2 has a child list 4 <-> 5, what is the value of curr.val after the first iteration of the outer while loop?
easy
A. 1
B. 4
C. 2
D. 3

Solution

  1. Step 1: Initial state

    curr starts at node with val=1. First iteration: curr=1, no child, move to curr.next=2.
  2. Step 2: First iteration with child

    curr=2 has child list starting at 4. The code finds tail=5, connects tail.next to curr.next (3), updates pointers, sets curr.next=4, child.prev=2, curr.child=None, then moves curr=curr.next=4.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    After first iteration, curr moves to child node 4 [OK]
Hint: After splicing child, curr moves to child's head node [OK]
Common Mistakes:
  • Assuming curr stays at original node after splicing
  • Forgetting to move curr to next after flattening
  • Confusing tail with child head
4. Consider the following buggy recursive code to convert a binary number in a linked list to an integer. Which line contains the subtle bug that causes incorrect output for single-node lists?
medium
A. Line X: using addition instead of bitwise OR to accumulate bits
B. Line 7: base case check for None node
C. Line 3: __init__ method of ListNode
D. Line 9: recursive call with node.next and updated acc

Solution

  1. Step 1: Identify the accumulation operation

    The code uses bitwise OR instead of addition to combine bits: acc = (acc << 1) | node.val.
  2. Step 2: Understand impact on single-node lists

    Bitwise OR correctly sets bits without carry, ensuring accurate accumulation for all list lengths.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Bitwise OR correctly sets bits without carry, addition may overflow [OK]
Hint: Use bitwise OR, not addition, to accumulate bits [OK]
Common Mistakes:
  • Using + instead of | causes wrong bit accumulation
  • Misunderstanding bitwise operations vs arithmetic
  • Assuming addition and OR are interchangeable for bits
5. What is the amortized time complexity of the visit, back, and forward operations in the two stacks approach for browser history, assuming n total operations?
medium
A. O(1) amortized per operation since each URL is pushed and popped at most once per stack
B. O(n) total for all operations combined, but O(1) worst-case per operation
C. O(log n) per operation due to stack resizing costs
D. O(n) per operation because each visit may clear the forward stack

Solution

  1. Step 1: Analyze push/pop operations per URL

    Each URL is pushed once onto back_stack and popped at most once to forward_stack, and vice versa.
  2. Step 2: Calculate amortized cost

    Since each URL moves between stacks a limited number of times, total operations over n steps average to O(1) per operation.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Amortized O(1) is standard for two stacks navigation [OK]
Hint: Each URL moves between stacks only a few times [OK]
Common Mistakes:
  • Assuming clearing forward stack is O(n) per visit
  • Confusing amortized with worst-case
  • Ignoring stack push/pop costs
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard