Linked List Cycle Length

🎯

Linked List Cycle Length

easyTWO_POINTERAmazonGoogle

Imagine you are debugging a network of pipes and want to find if water flows in a loop, and if so, how long that loop is.

💡 This problem involves detecting a cycle in a linked list and then measuring its length. Beginners often struggle because they don't know how to detect cycles efficiently or how to count the cycle length once detected. Understanding the fast and slow pointer technique is key.

📋

Problem Statement

Given the head of a singly linked list, determine if the linked list contains a cycle. If a cycle exists, return the length of the cycle (the number of nodes in the cycle). If there is no cycle, return 0.

The number of nodes in the list is in the range [0, 10^5].Node values can be any integer.You must solve the problem using O(1) additional space.

💡

Example

Input"head = [3,2,0,-4], where the tail connects to the node at position 1 (0-indexed)"

Output3

The cycle is formed by nodes with values 2 -> 0 -> -4 -> back to 2, so the cycle length is 3.

Input"head = [1,2], where the tail connects to the node at position 0"

Output2

The cycle includes nodes 1 and 2, so the length is 2.

Input"head = [1], no cycle"

Output0

No cycle exists, so the output is 0.

• Empty list (head = null) → 0
• Single node with no cycle → 0
• Single node with cycle to itself → 1
• Cycle at the very end of the list → length of cycle
• Long list with no cycle → 0

⚠️

Common Mistakes

Not checking if fast and fast.next are null before advancing fast pointer

Runtime error due to null pointer dereference

✅ Always check fast and fast.next are not null before moving fast pointer

Counting cycle length incorrectly by moving the wrong pointer or off-by-one errors

Incorrect cycle length returned

✅ After detecting cycle, move one pointer step by step until it meets the other pointer again, counting steps carefully

Using extra space when the problem expects O(1) space

Suboptimal solution that may be rejected in interviews

✅ Use fast and slow pointer technique instead of hash sets

Not handling edge cases like empty list or single node with cycle

Incorrect output or runtime errors

✅ Add explicit checks for empty list and single node cases

🧠

Brute Force (Hash Set to Detect Cycle and Count Length)

💡 This approach uses extra memory to store visited nodes. It is straightforward and helps beginners understand cycle detection by explicitly tracking visited nodes, but it is not optimal in space.

Intuition

Traverse the linked list and store each visited node in a hash set. When a node repeats, a cycle is detected. Then, count the number of nodes in the cycle by traversing from the repeated node until you come back to it.

Algorithm

1. Initialize an empty hash set to store visited nodes.
2. Traverse the linked list node by node.
3. If the current node is already in the set, a cycle is detected; break.
4. If no cycle is detected, return 0.
5. If a cycle is detected, start from the repeated node and count nodes until you return to it to find the cycle length.

💡 This algorithm is easy to follow but requires extra memory, which is not ideal for large lists.

</>

Code

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

def cycle_length(head):
    visited = set()
    current = head
    while current:
        if current in visited:
            # Cycle detected, count length
            length = 1
            node = current.next
            while node != current:
                length += 1
                node = node.next
            return length
        visited.add(current)
        current = current.next
    return 0

# Example usage:
if __name__ == '__main__':
    # Create a cycle list: 3->2->0->-4->2...
    node1 = ListNode(3)
    node2 = ListNode(2)
    node3 = ListNode(0)
    node4 = ListNode(-4)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node2  # cycle here
    print(cycle_length(node1))  # Output: 3

Line Notes

visited = set()Initialize a set to keep track of visited nodes to detect repeats.

while current:Traverse the linked list until the end or a cycle is found.

if current in visited:Check if current node was seen before, indicating a cycle.

while node != current:Count nodes in the cycle by looping until we return to the start node.

import java.util.HashSet;

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

public class Solution {
    public static int cycleLength(ListNode head) {
        HashSet<ListNode> visited = new HashSet<>();
        ListNode current = head;
        while (current != null) {
            if (visited.contains(current)) {
                int length = 1;
                ListNode node = current.next;
                while (node != current) {
                    length++;
                    node = node.next;
                }
                return length;
            }
            visited.add(current);
            current = current.next;
        }
        return 0;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(-4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2; // cycle
        System.out.println(cycleLength(node1)); // Output: 3
    }
}

Line Notes

HashSet<ListNode> visited = new HashSet<>();Use a hash set to track visited nodes for cycle detection.

while (current != null)Traverse the linked list until the end or cycle found.

if (visited.contains(current))Detect cycle when a node is revisited.

while (node != current)Count the cycle length by iterating until back to start node.

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

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

int cycleLength(ListNode* head) {
    unordered_set<ListNode*> visited;
    ListNode* current = head;
    while (current != nullptr) {
        if (visited.find(current) != visited.end()) {
            int length = 1;
            ListNode* node = current->next;
            while (node != current) {
                length++;
                node = node->next;
            }
            return length;
        }
        visited.insert(current);
        current = current->next;
    }
    return 0;
}

int main() {
    ListNode* node1 = new ListNode(3);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(0);
    ListNode* node4 = new ListNode(-4);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node2; // cycle
    cout << cycleLength(node1) << endl; // Output: 3
    return 0;
}

Line Notes

unordered_set<ListNode*> visited;Use unordered_set to store visited nodes for O(1) lookup.

while (current != nullptr)Traverse nodes until end or cycle detected.

if (visited.find(current) != visited.end())Detect cycle by checking if node was visited before.

while (node != current)Count cycle length by iterating until back to start node.

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

function cycleLength(head) {
    const visited = new Set();
    let current = head;
    while (current !== null) {
        if (visited.has(current)) {
            let length = 1;
            let node = current.next;
            while (node !== current) {
                length++;
                node = node.next;
            }
            return length;
        }
        visited.add(current);
        current = current.next;
    }
    return 0;
}

// Example usage:
const node1 = new ListNode(3);
const node2 = new ListNode(2);
const node3 = new ListNode(0);
const node4 = new ListNode(-4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2; // cycle
console.log(cycleLength(node1)); // Output: 3

Line Notes

const visited = new Set();Create a set to track visited nodes for cycle detection.

while (current !== null)Traverse the linked list until no more nodes or cycle found.

if (visited.has(current))Detect cycle when a node is revisited.

while (node !== current)Count the cycle length by looping until back to start node.

⏱

Complexity

TimeO(n)

SpaceO(n)

We traverse each node once and store each in a hash set, so time is linear. Space is linear due to the hash set storing nodes.

💡 For n=100,000 nodes, this means up to 100,000 insertions and lookups in the set, which is feasible but uses extra memory.

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 interviews expecting O(1) space.

🧠

Fast and Slow Pointer to Detect Cycle, Then Count Length

💡 This approach uses two pointers moving at different speeds to detect a cycle without extra space. It is a classic technique that is efficient and commonly expected in interviews.

Intuition

Use two pointers: slow moves one step at a time, fast moves two steps. If they meet, a cycle exists. Then, to find the cycle length, keep one pointer fixed and move the other until it meets again, counting steps.

Algorithm

1. Initialize two pointers, slow and fast, at the head.
2. Move slow by one step and fast by two steps until they meet or fast reaches the end.
3. If no meeting point, return 0 (no cycle).
4. If they meet, keep slow fixed and move fast one step at a time, counting steps until fast meets slow again.
5. Return the count as the cycle length.

💡 This algorithm cleverly uses pointer speeds to detect cycles and then counts cycle length efficiently.

</>

Code

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

def cycle_length(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # Cycle detected, count length
            length = 1
            fast = fast.next
            while fast != slow:
                length += 1
                fast = fast.next
            return length
    return 0

# Example usage:
if __name__ == '__main__':
    node1 = ListNode(3)
    node2 = ListNode(2)
    node3 = ListNode(0)
    node4 = ListNode(-4)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node2
    print(cycle_length(node1))  # Output: 3

Line Notes

slow = fast = headInitialize both pointers at the start of the list.

while fast and fast.next:Ensure fast pointer and its next node exist to avoid null errors.

if slow == fast:Pointers meet means a cycle is detected.

while fast != slow:Count cycle length by moving fast until it meets slow again.

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

public class Solution {
    public static int cycleLength(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                int length = 1;
                fast = fast.next;
                while (fast != slow) {
                    length++;
                    fast = fast.next;
                }
                return length;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(-4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2;
        System.out.println(cycleLength(node1)); // Output: 3
    }
}

Line Notes

ListNode slow = head, fast = head;Initialize slow and fast pointers at the head.

while (fast != null && fast.next != null)Check fast pointer and next to avoid null pointer exceptions.

if (slow == fast)Detect cycle when pointers meet.

while (fast != slow)Count cycle length by moving fast until it meets slow again.

#include <iostream>
using namespace std;

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

int cycleLength(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            int length = 1;
            fast = fast->next;
            while (fast != slow) {
                length++;
                fast = fast->next;
            }
            return length;
        }
    }
    return 0;
}

int main() {
    ListNode* node1 = new ListNode(3);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(0);
    ListNode* node4 = new ListNode(-4);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node2;
    cout << cycleLength(node1) << endl; // Output: 3
    return 0;
}

Line Notes

ListNode* slow = head;Initialize slow pointer at head.

while (fast && fast->next)Ensure fast pointer and next exist to avoid null dereference.

if (slow == fast)Cycle detected when pointers meet.

while (fast != slow)Count cycle length by moving fast until it meets slow.

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

function cycleLength(head) {
    let slow = head, fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            let length = 1;
            fast = fast.next;
            while (fast !== slow) {
                length++;
                fast = fast.next;
            }
            return length;
        }
    }
    return 0;
}

// Example usage:
const node1 = new ListNode(3);
const node2 = new ListNode(2);
const node3 = new ListNode(0);
const node4 = new ListNode(-4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2;
console.log(cycleLength(node1)); // Output: 3

Line Notes

let slow = head, fast = head;Initialize two pointers at the start.

while (fast !== null && fast.next !== null)Check pointers to avoid null errors.

if (slow === fast)Detect cycle when pointers meet.

while (fast !== slow)Count cycle length by moving fast until it meets slow.

⏱

Complexity

TimeO(n)

SpaceO(1)

Each node is visited at most a constant number of times by the pointers, so time is linear. Space is constant as no extra data structures are used.

💡 For n=100,000 nodes, this means about 100,000 steps, which is efficient and uses minimal memory.

Interview Verdict: Accepted and optimal

This is the preferred approach in interviews due to its efficiency and constant space usage.

🧠

Optimized Fast-Slow Pointer with Early Exit and Cycle Length Counting

💡 This approach is a slight optimization of the classic fast-slow pointer method, adding early exit checks and clearer cycle length counting logic to improve readability and efficiency.

Intuition

Detect cycle with fast and slow pointers. Once detected, move one pointer step by step counting nodes until it meets the other pointer again to find cycle length. Early exit if no cycle.

Algorithm

1. Initialize slow and fast pointers at head.
2. Move slow by one and fast by two steps until they meet or fast reaches null.
3. If no meeting, return 0.
4. Set a counter to 1 and move slow one step at a time until it meets fast again, incrementing counter.
5. Return the counter as the cycle length.

💡 This approach emphasizes clarity and early termination to avoid unnecessary iterations.

</>

Code

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

def cycle_length(head):
    if not head:
        return 0
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            length = 1
            slow = slow.next
            while slow != fast:
                length += 1
                slow = slow.next
            return length
    return 0

# Example usage:
if __name__ == '__main__':
    node1 = ListNode(3)
    node2 = ListNode(2)
    node3 = ListNode(0)
    node4 = ListNode(-4)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node2
    print(cycle_length(node1))  # Output: 3

Line Notes

if not head:Handle empty list edge case immediately.

while fast and fast.next:Ensure pointers are valid to avoid errors.

if slow == fast:Detect cycle when pointers meet.

while slow != fast:Count cycle length by moving slow until it meets fast again.

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

public class Solution {
    public static int cycleLength(ListNode head) {
        if (head == null) return 0;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                int length = 1;
                slow = slow.next;
                while (slow != fast) {
                    length++;
                    slow = slow.next;
                }
                return length;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(-4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2;
        System.out.println(cycleLength(node1)); // Output: 3
    }
}

Line Notes

if (head == null) return 0;Handle empty list early to avoid unnecessary processing.

while (fast != null && fast.next != null)Check pointers to prevent null pointer exceptions.

if (slow == fast)Cycle detected when pointers meet.

while (slow != fast)Count cycle length by moving slow until it meets fast.

#include <iostream>
using namespace std;

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

int cycleLength(ListNode* head) {
    if (!head) return 0;
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            int length = 1;
            slow = slow->next;
            while (slow != fast) {
                length++;
                slow = slow->next;
            }
            return length;
        }
    }
    return 0;
}

int main() {
    ListNode* node1 = new ListNode(3);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(0);
    ListNode* node4 = new ListNode(-4);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node2;
    cout << cycleLength(node1) << endl; // Output: 3
    return 0;
}

Line Notes

if (!head) return 0;Return immediately if list is empty.

while (fast && fast->next)Check pointers to avoid null dereference.

if (slow == fast)Detect cycle when pointers meet.

while (slow != fast)Count cycle length by moving slow until it meets fast.

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

function cycleLength(head) {
    if (!head) return 0;
    let slow = head, fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            let length = 1;
            slow = slow.next;
            while (slow !== fast) {
                length++;
                slow = slow.next;
            }
            return length;
        }
    }
    return 0;
}

// Example usage:
const node1 = new ListNode(3);
const node2 = new ListNode(2);
const node3 = new ListNode(0);
const node4 = new ListNode(-4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2;
console.log(cycleLength(node1)); // Output: 3

Line Notes

if (!head) return 0;Handle empty list edge case immediately.

while (fast !== null && fast.next !== null)Check pointers to avoid runtime errors.

if (slow === fast)Detect cycle when pointers meet.

while (slow !== fast)Count cycle length by moving slow until it meets fast.

⏱

Complexity

TimeO(n)

SpaceO(1)

The algorithm visits each node a constant number of times, so time is linear. Space is constant as no extra data structures are used.

💡 This approach is efficient for large inputs and uses minimal memory, ideal for interviews.

Interview Verdict: Accepted and optimal with minor improvements

This approach is a polished version of the classic fast-slow pointer method, showing good coding style and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, the fast and slow pointer approach (Approach 2 or 3) is the best to code due to its optimal time and space. The brute force approach is useful to mention but not to implement.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Hash Set)	O(n)	O(n)	No	Yes	Mention only - never code
2. Fast and Slow Pointer	O(n)	O(1)	No	Yes	Code this approach
3. Optimized Fast-Slow Pointer	O(n)	O(1)	No	Yes	Code this approach if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach, followed by the optimal fast-slow pointer method. Practice coding and testing edge cases.

How to Present

Clarify the problem and constraints with the interviewer.Describe the brute force approach using a hash set to detect cycles.Explain its drawbacks (extra space) and introduce the fast and slow pointer technique.Detail how to detect the cycle and count its length using pointers.Write clean, tested code and discuss edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of cycle detection, pointer manipulation, and ability to optimize space. They also check your handling of edge cases and code correctness.

Common Follow-ups

• What if you need to find the node where the cycle begins? → Use fast-slow pointers and reset one pointer to head, move both one step until they meet.
• Can you detect cycle length without counting nodes explicitly? → No, counting nodes in the cycle requires traversal.

💡 These follow-ups test deeper understanding of cycle detection and pointer techniques.

🔍

Pattern Recognition

When to Use

1) Problem involves linked list or sequence traversal; 2) Need to detect cycles or loops; 3) Constraints require O(1) space; 4) Counting or detecting repeated nodes.

Signature Phrases

detect cycle in linked listfind length of cyclefast and slow pointers

NOT This Pattern When

Problems that require reversing linked lists or sorting arrays are different patterns.

Similar Problems

Linked List Cycle Detection - detect if cycle existsHappy Number - detect cycle in number sequenceFind the Duplicate Number - detect cycle in array indices

Practice

1. Consider the following Python function that deletes N nodes after skipping M nodes in a linked list. Given the linked list 1 -> 2 -> 3 -> 4 and parameters M=1, N=1, what is the linked list after calling delete_n_after_m_optimized(head, 1, 1)?

easy

A. 1 -> 3 -> 4

B. 2 -> 3 -> 4

C. 1 -> 2 -> 4

D. 1 -> 4

Solution

1. Step 1: Trace skipping M=1 node

   Starting at node 1, skip 1 node means stay at node 1 (loop runs zero times).

2. Step 2: Delete N=1 node after current

   Delete node after 1, which is node 2. So, link node 1's next to node 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Resulting list is 1 -> 3 -> 4 after deletion [OK]

Hint: Skipping M=1 means no move; delete next N=1 node [OK]

Common Mistakes:

• Off-by-one in skipping nodes
• Deleting wrong nodes after skipping
• Misunderstanding loop ranges

2. Consider the following code that detects a cycle by marking nodes as visited. Given the linked list: 1 -> 2 -> 3 -> 4 -> 2 (cycle back to node with value 2), what is the output of hasCycle(node1)?

easy

A. true

B. false

C. null

D. Runtime error due to infinite loop

Solution

1. Step 1: Trace the traversal and marking of nodes

   Start at node1 (visited=false), mark visited=true, move to node2. Repeat for node2 and node3. When reaching node4, mark visited=true and move to node2 again, which is already visited.

2. Step 2: Detect cycle when revisiting node2

   Since node2.visited is true, the function returns true indicating a cycle.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle detected correctly by visited flag [OK]

Hint: Cycle detected when revisiting a marked node [OK]

Common Mistakes:

• Assuming no cycle due to missing pointer update
• Confusing return values

3. What is the time complexity of the optimized fast and slow pointer approach for detecting a circular array loop in an array of length n?

medium

A. O(n^2) because each element may be visited multiple times

B. O(n log n) due to repeated modulo operations and pointer jumps

C. O(n) because each element is visited at most once due to marking visited elements

D. O(n) amortized but worst case can be O(n^2) if cycles overlap

Solution

1. Step 1: Identify outer loop and inner pointer movements

   The outer loop runs n times, but elements are marked zero once visited, preventing reprocessing.

2. Step 2: Analyze pointer visits

   Each element is visited at most once in the inner while loop due to zero marking, so total work is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Marking visited elements ensures linear time complexity [OK]

Hint: Marking visited elements prevents repeated work -> O(n) [OK]

Common Mistakes:

• Assuming repeated visits cause O(n^2)
• Confusing modulo cost as log factor
• Believing overlapping cycles increase complexity

4. What is the time and space complexity of the optimal single-pass two-pointer approach to find the middle node of a singly linked list with n nodes?

medium

A. Time: O(n), Space: O(1)

B. Time: O(n^2), Space: O(1)

C. Time: O(n), Space: O(n)

D. Time: O(log n), Space: O(1)

Solution

1. Step 1: Identify time complexity

   Fast pointer moves two steps per iteration, slow moves one; total iterations proportional to n -> O(n) time.

2. Step 2: Identify space complexity

   Only two pointers used, no extra data structures -> O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and constant space for two-pointer traversal [OK]

Hint: Two pointers traverse list once, no extra storage [OK]

Common Mistakes:

• Confusing space with O(n) due to recursion
• Assuming nested loops cause O(n^2)
• Thinking fast pointer halves complexity to O(log n)

5. What is the space complexity of the stack-based approach to find the nth node from the end in a singly linked list of length n?

medium

A. O(n) because all nodes are stored in the stack

B. O(1) because only a few pointers are used

C. O(n) because recursion stack is used

D. O(log n) due to divide and conquer traversal

Solution

1. Step 1: Identify data structures used

   The stack stores every node in the list, so it holds n nodes.

2. Step 2: Determine space complexity

   Storing all n nodes means O(n) auxiliary space is required.

3. Step 3: Re-examine options

   O(n) because all nodes are stored in the stack states O(n) space which is correct for stack-based approach. O(1) because only a few pointers are used states O(1) which is incorrect for stack-based approach.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Stack size grows linearly with list length [OK]

Hint: Stack stores all nodes, so space is O(n) [OK]

Common Mistakes:

• Assuming constant space due to pointers
• Confusing recursion stack with iterative stack
• Thinking divide and conquer applies here