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. Given the following code snippet for detecting a circular array loop, what is the return value when the input is nums = [2, -1, 1, 2, 2]?

easy

A. True

B. False

C. Raises an IndexError

D. Infinite loop

Solution

1. Step 1: Trace first iteration starting at index 0

   nums[0]=2 (positive), direction is forward. slow and fast start at 0.

2. Step 2: Move slow and fast pointers

   slow moves to index (0+2)%5=2, fast moves two steps: first to 2, then to (2+1)%5=3. Both nums[2] and nums[3] are positive, direction consistent.

3. Step 3: Next iteration

   slow moves to (2+1)%5=3, fast moves two steps: from 3 to (3+2)%5=0, then from 0 to (0+2)%5=2. slow=3, fast=2, not equal yet.

4. Step 4: Next iteration

   slow moves to (3+2)%5=0, fast moves two steps: from 2 to (2+1)%5=3, then from 3 to (3+2)%5=0. slow=0, fast=0, pointers meet.

5. Step 5: Check cycle length

   Check if slow == next_index(slow): next_index(0) = 2, not equal, so cycle length > 1.

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   Cycle detected with consistent direction and length > 1 [OK]

Hint: Pointers meet at index 0 with valid cycle -> returns True [OK]

Common Mistakes:

• Confusing slow and fast pointer positions
• Ignoring direction check
• Mistaking single-element loop as valid

2. Given the following code snippet, what is the output when calling findDuplicate([3,1,3,4,2])?

easy

A. 3

B. 1

C. 4

D. 2

Solution

1. Step 1: Trace first phase to find intersection point

   Initialize slow=3, fast=3 (nums[0]=3). Iteration 1: slow=nums[3]=4, fast=nums[nums[3]]=nums[4]=2. Iteration 2: slow=nums[4]=2, fast=nums[nums[2]]=nums[3]=4. Iteration 3: slow=nums[2]=3, fast=nums[nums[4]]=nums[2]=3. They meet at 3.

2. Step 2: Trace second phase to find cycle entrance

   Reset slow=nums[0]=3. Since slow==fast==3, loop ends immediately. Return 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle detection returns duplicate 3 correctly [OK]

Hint: Cycle detection returns the duplicate value where pointers meet [OK]

Common Mistakes:

• Confusing slow and fast pointer updates
• Off-by-one errors in indexing
• Returning the wrong pointer value

3. What is the time complexity of the optimized iterative approach for deleting N nodes after skipping M nodes in a singly linked list of length n? Assume M and N are constants.

medium

A. O(n)

B. O(n * (M + N))

C. O(n^2)

D. O(n + M + N)

Solution

1. Step 1: Identify loop behavior

   The algorithm traverses the list once, moving forward by skipping M nodes and deleting N nodes repeatedly.

2. Step 2: Analyze complexity

   Since M and N are constants, each iteration moves forward by at least M+N nodes, so total steps proportional to n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass traversal yields O(n) time complexity [OK]

Hint: Constant M, N means linear traversal dominates [OK]

Common Mistakes:

• Mistaking nested loops causing O(n*(M+N))
• Assuming quadratic due to inner loops
• Ignoring that M and N are constants

4. What is the time complexity of the optimal Happy Number detection algorithm that uses a known cycle set and repeatedly computes the sum of squares of digits until it reaches 1 or a cycle number? Assume n is the input number and k is the number of iterations until termination.

medium

A. O(n) because each digit is processed once per iteration

B. O(k * log n) because each iteration processes digits proportional to log n and there are k iterations

C. O(k * n) because sum of squares depends on n itself

D. O(k) because the cycle detection set lookup is constant time and digits are fixed length

Solution

1. Step 1: Identify cost per iteration

   Each iteration computes sum of squares of digits. Number of digits in n is proportional to log n, so each iteration is O(log n).

2. Step 2: Multiply by number of iterations k

   The process repeats k times until reaching 1 or cycle. Total time is O(k * log n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum of digits per iteration is log n, repeated k times -> O(k * log n) [OK]

Hint: Sum of digits cost is O(log n), not O(n) [OK]

Common Mistakes:

• Confusing n with number of digits, assuming O(n) per iteration

5. What is the space complexity of the optimal palindrome linked list check that reverses the second half in-place?

medium

A. O(n) due to storing node values in an array

B. O(1) because reversal is done in-place without extra data structures

C. O(log n) due to recursion stack in reversal

D. O(n) due to recursion stack in reversal

Solution

1. Step 1: Identify auxiliary space usage

   The algorithm reverses the second half in-place using pointers, no extra arrays or stacks.

2. Step 2: Check for recursion stack

   The reversal is iterative, so no recursion stack space is used.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   In-place iterative reversal uses constant extra space [OK]

Hint: Iterative reversal uses O(1) space, recursion would add stack space [OK]

Common Mistakes:

• Confusing iterative reversal with recursive reversal
• Assuming array storage is needed for palindrome check
• Forgetting recursion stack space in complexity