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. Consider the following buggy code snippet for detecting a circular array loop. Which line contains the subtle bug that causes incorrect detection of single-element loops as valid cycles?

medium

A. Line with 'if nums[i] == 0: continue' - skipping zeros prematurely

B. Line with 'if slow == fast: return True' - missing check for single-element loop

C. Line with 'direction = nums[i] > 0' - direction assignment incorrect

D. Line with 'nums[slow] = 0' - zeroing visited elements too early

Solution

1. Step 1: Identify where single-element loops are checked

   The original code breaks if slow == next_index(slow) to avoid single-element loops.

2. Step 2: Locate missing check

   The buggy code returns True immediately when slow == fast without verifying cycle length.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing single-element loop check causes false positives [OK]

Hint: Check cycle length before returning True to avoid single-element loops [OK]

Common Mistakes:

• Returning True immediately on pointer meet
• Ignoring direction consistency
• Incorrectly zeroing elements

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

3. Identify the bug in the following code snippet for detecting and returning the cycle length in a linked list.

medium

A. Line 11: The length counting loop should start with length = 0 instead of 1.

B. Line 6: slow pointer should move two steps instead of one.

C. Line 7: fast pointer should move one step instead of two.

D. Line 4: The condition should check both fast and fast.next to avoid null pointer errors.

Solution

1. Step 1: Check loop condition for pointer safety

   The loop condition only checks if fast is not null, but fast.next may be null causing runtime error on fast.next.next.

2. Step 2: Confirm other lines are correct

   Slow moves one step, fast moves two steps correctly; length counting starts at 1 correctly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing fast.next check causes null pointer dereference [OK]

Hint: Always check fast and fast.next before advancing fast by two steps [OK]

Common Mistakes:

• Forgetting fast.next check
• Off-by-one in length counting
• Swapping slow and fast pointer steps

4. Consider this buggy code snippet for finding the nth node from the end using two pointers. Which line contains the bug?

medium

A. Line 9: return statement returning slow pointer

B. Line 7: while loop condition

C. Line 3: for loop advancing fast pointer

D. Line 2: initializing slow pointer

Solution

1. Step 1: Analyze return statement

   The function returns the slow pointer node instead of its value, which is inconsistent with expected output.

2. Step 2: Confirm other lines are correct

   Fast pointer advances n-1 steps, loop condition is correct, and slow pointer initialization is standard.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Returning node instead of value causes confusion or errors [OK]

Hint: Return node.val, not node reference [OK]

Common Mistakes:

• Not checking if n > length
• Advancing fast pointer fewer steps
• Returning node instead of value

5. Suppose the problem is modified so that elements in the array can be reused multiple times in cycles (i.e., cycles can revisit indices multiple times), and the direction constraint is removed. Which of the following modifications to the algorithm correctly detects cycles under these new conditions?

hard

A. Use the original fast-slow pointer approach but ignore direction checks and cycle length > 1 condition

B. Use a visited set to track all visited indices globally and detect any repeated index during traversal

C. Modify fast-slow pointer to allow revisiting indices multiple times and remove in-place marking

D. Run DFS from each index without direction checks and detect back edges to find cycles

Solution

1. Step 1: Understand new problem constraints

   Cycles can revisit indices multiple times and direction constraint is removed, so fast-slow pointer is insufficient.

2. Step 2: Identify correct cycle detection method

   DFS with back edge detection in a graph representation correctly detects cycles without direction or length constraints.

3. Step 3: Evaluate other options

   Original fast-slow pointer fails without direction; visited set alone is insufficient for complex cycles; modifying fast-slow pointer to allow revisits breaks cycle detection logic.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   DFS with back edges is standard for cycle detection in general graphs [OK]

Hint: Without direction, use DFS and back edge detection [OK]

Common Mistakes:

• Assuming fast-slow pointer works without direction
• Ignoring multiple revisits
• Using visited set without cycle structure