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

🎯

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.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(n)	No	Yes	Mention only - never code due to extra space
2. Better (Fast-Slow + Reverse + Merge)	O(n)	O(1)	No	Yes	Code this approach for optimal solution
3. Recursive Reordering	O(n)	O(n) due to recursion stack	Yes	Yes	Mention 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. 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

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

3. Identify the bug in the following code snippet implementing the odd-even linked list rearrangement:

def oddEvenList(head):
    if not head or not head.next:
        return head
    odd = head
    even = head.next
    even_head = even
    while even and even.next:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next
    # Missing termination of even list
    odd.next = even_head
    return head

What is the consequence of the missing line and how to fix it?

medium

A. The function does not handle empty lists; fix by adding a check for head == None at the start

B. The odd pointer is not updated correctly inside the loop; fix by moving 'odd = odd.next' after even pointer updates

C. The even_head pointer is lost; fix by initializing even_head after the loop instead of before

D. The even list is not terminated with null, causing a cycle; fix by adding 'if even: even.next = None' before linking odd.next

Solution

1. Step 1: Understand pointer termination

   Without setting even.next = None, the even list may still point to old nodes, causing cycles or infinite loops.

2. Step 2: Fix by terminating even list

   Adding 'if even: even.next = None' before linking odd.next ensures even list ends properly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Proper termination prevents cycles and infinite traversal [OK]

Hint: Always terminate the last node's next with None to avoid cycles [OK]

Common Mistakes:

• Forgetting to terminate even list causing infinite loops
• Misplacing pointer updates causing node skips

4. What is the time complexity of the optimal in-place split algorithm for splitting a linked list of length n into k parts, and why?

medium

A. O(n) because splitting is done in a single pass without extra overhead.

B. O(n * k) because for each part, we traverse nodes up to part size.

C. O(n + k) because we first count nodes in one pass, then split in one pass plus overhead for k parts.

D. O(k) because the algorithm mainly depends on the number of parts.

Solution

1. Step 1: Identify passes over the list

   One pass to count total nodes (O(n)), one pass to split nodes into k parts (O(n)).

2. Step 2: Account for overhead

   Creating dummy heads and managing k parts adds O(k) overhead, but does not dominate.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two passes over n plus O(k) overhead is O(n), since k ≤ n [OK]

Hint: Counting + splitting passes plus k overhead -> O(n) [OK]

Common Mistakes:

• Assuming nested loops cause O(n*k)
• Ignoring overhead of dummy heads
• Confusing single pass with O(n) ignoring k

5. Suppose the linked list can be extremely long (millions of nodes), causing recursion stack overflow in the recursive solution. Which modification is the best to handle this scenario efficiently?

hard

A. Increase the recursion limit to accommodate the large linked list depth.

B. Switch to an iterative approach that accumulates the decimal value using bit shifts.

C. Use a divide-and-conquer recursive approach to reduce recursion depth.

D. Convert the linked list to a string first, then parse the binary string to integer.

Solution

1. Step 1: Identify the problem with recursion

   Deep recursion causes stack overflow for very long linked lists.

2. Step 2: Evaluate alternatives

   Increasing recursion limit is risky and platform-dependent; divide-and-conquer adds complexity without reducing total depth; string conversion is inefficient.

3. Step 3: Choose iterative approach

   Iterative bitwise accumulation uses constant stack space and linear time, handling large inputs safely.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Iterative approach avoids recursion stack overflow [OK]

Hint: Iterative avoids recursion stack overflow on large inputs [OK]

Common Mistakes:

• Relying on recursion limit increase which is unsafe
• Assuming divide-and-conquer reduces recursion depth effectively
• Using string conversion which is inefficient for large inputs