Palindrome Linked List

🎯

Palindrome Linked List

easyTWO_POINTERAmazonFacebookMicrosoft

Imagine you have a chain of beads and want to check if the sequence of colors reads the same forwards and backwards without rearranging them.

💡 This problem tests your understanding of linked lists and two-pointer techniques. Beginners often struggle because linked lists don't allow direct indexing, making it tricky to compare elements from both ends efficiently.

📋

Problem Statement

Given the head of a singly linked list, determine if the linked list is a palindrome. Return true if it is, and false otherwise.

1 ≤ n ≤ 10^5Node values are integersExpected time complexity: O(n)Expected space complexity: O(1) or O(n) depending on approach

💡

Example

Input"head = [1, 2, 2, 1]"

Outputtrue

The list reads the same forwards and backwards.

Input"head = [1, 2]"

Outputfalse

The list is not the same forwards and backwards.

• Single node list → true
• List with all identical elements → true
• List with two different elements → false
• Empty list (if allowed) → true

⚠️

Common Mistakes

Not handling odd length lists correctly

Incorrect comparison leading to false negatives

✅ Skip the middle element when list length is odd before comparison

Not restoring the list after reversing second half

Modifies input list unexpectedly, which may cause issues in real applications

✅ Reverse the second half again after comparison to restore original list

Using extra space unnecessarily in optimal approach

Fails to meet O(1) space requirement

✅ Avoid stacks or arrays; reverse second half in place instead

Incorrectly finding the midpoint with fast and slow pointers

Leads to wrong half being reversed or compared

✅ Advance fast pointer by two steps and slow by one until fast reaches end

Not checking for empty or single node lists

Code may crash or return wrong result

✅ Add base case checks for empty or single node lists returning true

🧠

Brute Force (Using Array Conversion)

💡 This approach exists to build intuition by simplifying the problem to array palindrome checking, which is easier to understand and implement for beginners.

Intuition

Convert the linked list into an array and then check if the array is a palindrome by comparing elements from both ends.

Algorithm

1. Traverse the linked list and copy all node values into an array.
2. Use two pointers, one at the start and one at the end of the array.
3. Compare elements at these pointers; if they differ, return false.
4. If all pairs match, return true.

💡 This algorithm is straightforward but requires extra space. It helps beginners understand the palindrome concept before optimizing.

</>

Code

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

def isPalindrome(head):
    vals = []
    current = head
    while current:
        vals.append(current.val)
        current = current.next
    left, right = 0, len(vals) - 1
    while left < right:
        if vals[left] != vals[right]:
            return False
        left += 1
        right -= 1
    return True

# Example usage:
if __name__ == '__main__':
    # Create linked list 1->2->2->1
    node4 = ListNode(1)
    node3 = ListNode(2, node4)
    node2 = ListNode(2, node3)
    node1 = ListNode(1, node2)
    print(isPalindrome(node1))  # Output: True

Line Notes

vals = []Initialize an empty list to store node values for easy access.

while current:Traverse the linked list to collect all values.

if vals[left] != vals[right]:Check if the current pair of elements differ, indicating not a palindrome.

return TrueIf all pairs match, confirm the list is a palindrome.

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public boolean isPalindrome(ListNode head) {
        ArrayList<Integer> vals = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            vals.add(current.val);
            current = current.next;
        }
        int left = 0, right = vals.size() - 1;
        while (left < right) {
            if (!vals.get(left).equals(vals.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode node4 = new ListNode(1);
        ListNode node3 = new ListNode(2); node3.next = node4;
        ListNode node2 = new ListNode(2); node2.next = node3;
        ListNode node1 = new ListNode(1); node1.next = node2;
        Solution sol = new Solution();
        System.out.println(sol.isPalindrome(node1)); // true
    }
}

Line Notes

ArrayList<Integer> vals = new ArrayList<>();Use dynamic array to store node values for random access.

while (current != null)Traverse the linked list to collect values.

if (!vals.get(left).equals(vals.get(right)))Compare elements from both ends to check palindrome property.

return true;Return true if all pairs match, confirming palindrome.

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

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

bool isPalindrome(ListNode* head) {
    vector<int> vals;
    ListNode* current = head;
    while (current != nullptr) {
        vals.push_back(current->val);
        current = current->next;
    }
    int left = 0, right = vals.size() - 1;
    while (left < right) {
        if (vals[left] != vals[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

int main() {
    ListNode* node4 = new ListNode(1);
    ListNode* node3 = new ListNode(2); node3->next = node4;
    ListNode* node2 = new ListNode(2); node2->next = node3;
    ListNode* node1 = new ListNode(1); node1->next = node2;
    cout << (isPalindrome(node1) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

vector<int> vals;Store node values in a vector for indexed access.

while (current != nullptr)Traverse linked list to collect values.

if (vals[left] != vals[right])Compare elements from both ends to detect mismatch.

return true;Return true if no mismatches found, confirming palindrome.

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function isPalindrome(head) {
    const vals = [];
    let current = head;
    while (current !== null) {
        vals.push(current.val);
        current = current.next;
    }
    let left = 0, right = vals.length - 1;
    while (left < right) {
        if (vals[left] !== vals[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

// Example usage:
const node4 = new ListNode(1);
const node3 = new ListNode(2, node4);
const node2 = new ListNode(2, node3);
const node1 = new ListNode(1, node2);
console.log(isPalindrome(node1)); // true

Line Notes

const vals = [];Create an array to hold node values for easy palindrome check.

while (current !== null)Traverse the linked list to collect all values.

if (vals[left] !== vals[right])Check if current pair of values differ, indicating not palindrome.

return true;Return true if all pairs match, confirming palindrome.

⏱

Complexity

TimeO(n)

SpaceO(n)

We traverse the list once to copy values (O(n)) and then check palindrome in O(n). Extra space is used for the array of size n.

💡 For n=100,000 nodes, this means 100,000 operations to copy and 100,000 to check, which is feasible but uses extra memory.

Interview Verdict: Accepted

This approach works but uses extra space, which might not be optimal for very large inputs.

🧠

Better (Fast & Slow Pointer + Stack)

💡 This approach improves space usage by only storing half the list's values, introducing the fast and slow pointer technique to find the midpoint.

Intuition

Use two pointers to find the middle of the list. Push the first half's values onto a stack, then compare the second half with the stack's top elements.

Algorithm

1. Initialize fast and slow pointers at head.
2. Move fast by two steps and slow by one step, pushing slow's values onto a stack.
3. When fast reaches the end, slow is at midpoint.
4. If list length is odd, skip the middle element.
5. Compare remaining list nodes with stack's top values.
6. If all match, return true; else false.

💡 This algorithm cleverly uses a stack to reverse the first half's values, enabling comparison without full array storage.

</>

Code

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

def isPalindrome(head):
    slow = fast = head
    stack = []
    while fast and fast.next:
        stack.append(slow.val)
        slow = slow.next
        fast = fast.next.next
    if fast:  # Odd length, skip middle
        slow = slow.next
    while slow:
        top = stack.pop()
        if top != slow.val:
            return False
        slow = slow.next
    return True

# Example usage:
if __name__ == '__main__':
    node4 = ListNode(1)
    node3 = ListNode(2, node4)
    node2 = ListNode(2, node3)
    node1 = ListNode(1, node2)
    print(isPalindrome(node1))  # Output: True

Line Notes

slow = fast = headInitialize two pointers to find midpoint efficiently.

while fast and fast.next:Advance fast by two and slow by one to find middle.

stack.append(slow.val)Store first half values to compare later.

if fast: # Odd length, skip middleSkip the middle element for odd-length lists.

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    public boolean isPalindrome(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            stack.push(slow.val);
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null) { // Odd length
            slow = slow.next;
        }
        while (slow != null) {
            if (stack.pop() != slow.val) {
                return false;
            }
            slow = slow.next;
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode node4 = new ListNode(1);
        ListNode node3 = new ListNode(2); node3.next = node4;
        ListNode node2 = new ListNode(2); node2.next = node3;
        ListNode node1 = new ListNode(1); node1.next = node2;
        Solution sol = new Solution();
        System.out.println(sol.isPalindrome(node1)); // true
    }
}

Line Notes

Stack<Integer> stack = new Stack<>();Use stack to store first half values for reverse comparison.

while (fast != null && fast.next != null)Move fast and slow pointers to find midpoint.

if (fast != null) { // Odd lengthSkip middle element for odd-length lists.

if (stack.pop() != slow.val)Compare second half values with stack top.

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

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

bool isPalindrome(ListNode* head) {
    stack<int> st;
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        st.push(slow->val);
        slow = slow->next;
        fast = fast->next->next;
    }
    if (fast != nullptr) { // Odd length
        slow = slow->next;
    }
    while (slow != nullptr) {
        if (st.top() != slow->val) {
            return false;
        }
        st.pop();
        slow = slow->next;
    }
    return true;
}

int main() {
    ListNode* node4 = new ListNode(1);
    ListNode* node3 = new ListNode(2); node3->next = node4;
    ListNode* node2 = new ListNode(2); node2->next = node3;
    ListNode* node1 = new ListNode(1); node1->next = node2;
    cout << (isPalindrome(node1) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

stack<int> st;Stack stores first half values for reverse order comparison.

while (fast != nullptr && fast->next != nullptr)Find midpoint using fast and slow pointers.

if (fast != nullptr) { // Odd lengthSkip middle node for odd-length lists.

if (st.top() != slow->val)Compare second half nodes with stack top values.

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function isPalindrome(head) {
    let slow = head, fast = head;
    const stack = [];
    while (fast !== null && fast.next !== null) {
        stack.push(slow.val);
        slow = slow.next;
        fast = fast.next.next;
    }
    if (fast !== null) { // Odd length
        slow = slow.next;
    }
    while (slow !== null) {
        if (stack.pop() !== slow.val) {
            return false;
        }
        slow = slow.next;
    }
    return true;
}

// Example usage:
const node4 = new ListNode(1);
const node3 = new ListNode(2, node4);
const node2 = new ListNode(2, node3);
const node1 = new ListNode(1, node2);
console.log(isPalindrome(node1)); // true

Line Notes

const stack = [];Stack holds first half values for reverse comparison.

while (fast !== null && fast.next !== null)Use fast and slow pointers to find midpoint.

if (fast !== null) { // Odd lengthSkip middle node for odd-length lists.

if (stack.pop() !== slow.val)Compare second half values with stack top.

⏱

Complexity

TimeO(n)

SpaceO(n/2) = O(n)

We traverse the list once to find midpoint and push half values onto stack, then compare second half in O(n). Space is reduced to half compared to brute force.

💡 For n=100,000, this means 50,000 values stored in stack, which is better but still uses extra memory.

Interview Verdict: Accepted

This approach is better than brute force in space but still not optimal for very large inputs.

🧠

Optimal (Reverse Second Half In-Place)

💡 This approach optimizes space by reversing the second half of the list in place, allowing direct comparison without extra memory.

Intuition

Find the middle of the list, reverse the second half in place, then compare the first half and reversed second half node by node.

Algorithm

1. Use fast and slow pointers to find the middle of the list.
2. Reverse the second half of the list starting from slow pointer.
3. Compare nodes from the start and from the reversed second half.
4. If all nodes match, the list is a palindrome.
5. Restore the list by reversing the second half again (optional).
6. Return the result.

💡 This algorithm is tricky because it modifies the list temporarily but uses constant space and linear time.

</>

Code

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

def reverse(head):
    prev = None
    current = head
    while current:
        nxt = current.next
        current.next = prev
        prev = current
        current = nxt
    return prev

def isPalindrome(head):
    if not head or not head.next:
        return True
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    second_half_start = reverse(slow)
    first_half_start = head
    second_half_copy = second_half_start
    result = True
    while second_half_start:
        if first_half_start.val != second_half_start.val:
            result = False
            break
        first_half_start = first_half_start.next
        second_half_start = second_half_start.next
    reverse(second_half_copy)  # Optional: restore list
    return result

# Example usage:
if __name__ == '__main__':
    node4 = ListNode(1)
    node3 = ListNode(2, node4)
    node2 = ListNode(2, node3)
    node1 = ListNode(1, node2)
    print(isPalindrome(node1))  # Output: True

Line Notes

def reverse(head):Helper function to reverse a linked list segment in place.

while fast and fast.next:Find midpoint using fast and slow pointers.

second_half_start = reverse(slow)Reverse second half starting from midpoint.

while second_half_start:Compare nodes from first half and reversed second half.

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Solution {
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        while (current != null) {
            ListNode nextTemp = current.next;
            current.next = prev;
            prev = current;
            current = nextTemp;
        }
        return prev;
    }

    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode secondHalfStart = reverse(slow);
        ListNode firstHalfStart = head;
        ListNode secondHalfCopy = secondHalfStart;
        boolean result = true;
        while (secondHalfStart != null) {
            if (firstHalfStart.val != secondHalfStart.val) {
                result = false;
                break;
            }
            firstHalfStart = firstHalfStart.next;
            secondHalfStart = secondHalfStart.next;
        }
        reverse(secondHalfCopy); // Optional restore
        return result;
    }

    public static void main(String[] args) {
        ListNode node4 = new ListNode(1);
        ListNode node3 = new ListNode(2); node3.next = node4;
        ListNode node2 = new ListNode(2); node2.next = node3;
        ListNode node1 = new ListNode(1); node1.next = node2;
        Solution sol = new Solution();
        System.out.println(sol.isPalindrome(node1)); // true
    }
}

Line Notes

private ListNode reverse(ListNode head)Reverse linked list segment in place to compare halves.

while (fast != null && fast.next != null)Find midpoint with fast and slow pointers.

ListNode secondHalfStart = reverse(slow);Reverse second half starting at midpoint.

while (secondHalfStart != null)Compare nodes from first half and reversed second half.

#include <iostream>
using namespace std;

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

ListNode* reverse(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* current = head;
    while (current != nullptr) {
        ListNode* nextTemp = current->next;
        current->next = prev;
        prev = current;
        current = nextTemp;
    }
    return prev;
}

bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* secondHalfStart = reverse(slow);
    ListNode* firstHalfStart = head;
    ListNode* secondHalfCopy = secondHalfStart;
    bool result = true;
    while (secondHalfStart) {
        if (firstHalfStart->val != secondHalfStart->val) {
            result = false;
            break;
        }
        firstHalfStart = firstHalfStart->next;
        secondHalfStart = secondHalfStart->next;
    }
    reverse(secondHalfCopy); // Optional restore
    return result;
}

int main() {
    ListNode* node4 = new ListNode(1);
    ListNode* node3 = new ListNode(2); node3->next = node4;
    ListNode* node2 = new ListNode(2); node2->next = node3;
    ListNode* node1 = new ListNode(1); node1->next = node2;
    cout << (isPalindrome(node1) ? "true" : "false") << endl; // true
    return 0;
}

Line Notes

ListNode* reverse(ListNode* head)Reverse linked list segment in place for comparison.

while (fast && fast->next)Find midpoint using fast and slow pointers.

ListNode* secondHalfStart = reverse(slow);Reverse second half starting at midpoint.

while (secondHalfStart)Compare nodes from first half and reversed second half.

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function reverse(head) {
    let prev = null;
    let current = head;
    while (current !== null) {
        let nextTemp = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
    }
    return prev;
}

function isPalindrome(head) {
    if (!head || !head.next) return true;
    let slow = head, fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    let secondHalfStart = reverse(slow);
    let firstHalfStart = head;
    let secondHalfCopy = secondHalfStart;
    let result = true;
    while (secondHalfStart !== null) {
        if (firstHalfStart.val !== secondHalfStart.val) {
            result = false;
            break;
        }
        firstHalfStart = firstHalfStart.next;
        secondHalfStart = secondHalfStart.next;
    }
    reverse(secondHalfCopy); // Optional restore
    return result;
}

// Example usage:
const node4 = new ListNode(1);
const node3 = new ListNode(2, node4);
const node2 = new ListNode(2, node3);
const node1 = new ListNode(1, node2);
console.log(isPalindrome(node1)); // true

Line Notes

function reverse(head)Reverse linked list segment in place for direct comparison.

while (fast !== null && fast.next !== null)Find midpoint using fast and slow pointers.

let secondHalfStart = reverse(slow);Reverse second half starting at midpoint.

while (secondHalfStart !== null)Compare nodes from first half and reversed second half.

⏱

Complexity

TimeO(n)

SpaceO(1)

We traverse the list to find midpoint, reverse half in place, and compare nodes, all in linear time with constant extra space.

💡 For n=100,000, this means 100,000 operations but minimal memory usage, making it scalable.

Interview Verdict: Accepted

This is the best approach for interviews as it meets optimal time and space requirements.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the optimal in-place reversal approach impresses most, but understanding brute force and stack methods helps build intuition.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(n)	No	N/A	Mention only - never code
2. Fast & Slow Pointer + Stack	O(n)	O(n/2)	No	N/A	Good to mention as improvement, but not optimal
3. Reverse Second Half In-Place	O(n)	O(1)	No	Yes (optional)	Code this approach in 95% of interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly during interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Present the brute force approach to show understanding.Step 3: Discuss improvements using fast and slow pointers with a stack.Step 4: Explain the optimal in-place reversal approach.Step 5: Code the optimal solution carefully and test edge cases.

Time Allocation

Clarify: 2min → Approach discussion: 5min → Coding: 10min → Testing & optimization: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your grasp of linked list traversal, two-pointer technique, space-time tradeoffs, and ability to write clean, bug-free code.

Common Follow-ups

• What if you cannot modify the linked list? → Use stack approach.
• How to restore the list after checking? → Reverse second half again.
• What if the list is doubly linked? → Could compare from both ends directly.
• Can you do it recursively? → Yes, but watch for stack overflow.

💡 These follow-ups test your flexibility and deeper understanding of the problem constraints and variations.

🔍

Pattern Recognition

When to Use

1) Need to check palindrome property on linked list; 2) No direct indexing available; 3) Fast and slow pointers can find midpoint; 4) Reversing part of list is feasible.

Signature Phrases

'determine if linked list is palindrome''fast and slow pointers''reverse second half'

NOT This Pattern When

Problems that require full sorting or dynamic programming are different patterns.

Similar Problems

Palindrome Number - similar palindrome check but on integer digitsLinked List Cycle - uses fast and slow pointers to detect cycles

Practice

1. You are given a circular array where each element represents the number of steps to move forward or backward. The goal is to determine if there exists a cycle where all moves are in the same direction and the cycle length is greater than 1. Which algorithmic approach guarantees an optimal O(n) time and O(1) space solution for this problem?

easy

A. Fast and slow pointer technique (Floyd's cycle detection) adapted for circular arrays with direction checks

B. Greedy approach that tries to jump as far as possible each time without revisiting indices

C. Dynamic programming to store reachable indices and cycle lengths

D. Brute force simulation with a visited set for each start index

Solution

1. Step 1: Understand problem constraints

   The problem requires detecting cycles in a circular array with direction consistency and cycle length > 1.

2. Step 2: Identify algorithm that efficiently detects cycles

   Fast and slow pointer (Floyd's cycle detection) can detect cycles in O(n) time and O(1) space, with added direction checks to ensure cycle validity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Fast-slow pointer is classic for cycle detection in sequences [OK]

Hint: Cycle detection in sequences -> fast-slow pointer [OK]

Common Mistakes:

• Thinking greedy jumps detect cycles correctly
• Assuming DP applies here
• Using brute force is optimal

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. The following code attempts to detect a cycle in a circular array using the fast-slow pointer approach. Identify the line containing the subtle bug that causes incorrect cycle detection.

medium

A. Line with 'return true' inside while loop returns prematurely

B. Line with 'if slow == fast:' missing cycle length check

C. Line with 'direction = nums[i] > 0' incorrectly sets direction

D. Line with 'nums[marker] = 0' incorrectly marks visited elements

Solution

1. Step 1: Identify cycle detection condition

   The code returns true immediately when slow == fast, but does not check if cycle length > 1.

2. Step 2: Understand why self-loop is invalid

   Cycle of length 1 (self-loop) is invalid; must check if slow != next_index(slow) before returning true.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing cycle length check causes false positives [OK]

Hint: Check cycle length > 1 to avoid self-loop false positives [OK]

Common Mistakes:

• Returning true on self-loop cycles
• Mixing directions
• Not marking visited nodes

4. What is the space complexity of the recursive reorderList implementation shown below, considering a linked list of length n?

medium

A. O(log n) -- recursion divides list in halves

B. O(1) -- only constant extra pointers used

C. O(n) -- recursion stack grows linearly with list length

D. O(n^2) -- nested recursive calls cause quadratic space

Solution

1. Step 1: Analyze recursion depth

   Each recursive call moves one node forward, so recursion depth is n.

2. Step 2: Determine space usage

   Each call adds a stack frame, so total auxiliary space is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Recursion stack grows linearly with input size [OK]

Hint: Recursion depth equals list length -> O(n) space [OK]

Common Mistakes:

• Assuming recursion is O(1) space
• Confusing recursion with divide-and-conquer
• Thinking nested calls multiply space

5. Consider the following buggy code snippet for reorderList. Which line contains the subtle bug that can cause infinite loops or cycles when traversing the reordered list?

medium

A. Line with 'if left == right or left.next == right:' missing 'right.next = None' termination

B. Line with 'if not right: return' -- base case missing

C. Line with 'if stop: return' -- premature termination

D. Line with 'left = tmp' -- left pointer not updated correctly

Solution

1. Step 1: Identify termination condition

   The code must set right.next = None when left meets right or adjacent to avoid cycles.

2. Step 2: Locate missing termination

   The commented line misses 'right.next = None', causing the list to form cycles.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing termination causes infinite traversal [OK]

Hint: Always terminate reordered list with null to avoid cycles [OK]

Common Mistakes:

• Forgetting to set right.next = null
• Misplacing stop flag
• Incorrect pointer updates