Citadel·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Citadel SWE interview with a linked list reversal question. Pretty standard algorithmic stuff but they wanted both iterative and recursive solutions, plus edge case handling, so it wasn't just 'write the loop and move on'.

Questions Asked (1)

Given the head of a singly linked list, reverse it and return the new head. Implement both an iterative and a recursive solution, and handle edge cases like an empty list or a single node.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The iterative part was fine, three pointers, walk the list, done.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem and edge cases, then explain the iterative approach with three pointers (prev, curr, next), followed by the recursive approach. Emphasize time and space complexity trade-offs and test with edge cases.

Pro tip: Mention that the recursive solution uses O(n) stack space, which can cause stack overflow for large lists, so iterative is preferred in production. Also, discuss tail recursion optimization if the language supports it.

1. Clarify and Define Edge Cases

Confirm the problem: reverse a singly linked list and return the new head. Identify edge cases: empty list (head == null), single node, and list with two nodes.

2. Iterative Approach

Explain using three pointers: prev (initially null), curr (head), and next. Iterate while curr != null, reversing the link and advancing pointers. Return prev as new head.

3. Recursive Approach

Define base case: if head is null or head.next is null, return head. Recursively reverse the rest, then set head.next.next = head and head.next = null. Return the new head from recursion.

4. Analyze Complexity and Trade-offs

Iterative: O(n) time, O(1) space. Recursive: O(n) time, O(n) space due to call stack. Discuss when to use each (e.g., iterative for large lists to avoid stack overflow).

5. Test with Edge Cases

Walk through examples: empty list, single node, two nodes, and a general list. Verify both implementations handle these correctly.

Key Points to Mention

Time complexity O(n) and space complexity O(1) for iterative, O(n) for recursive due to call stack.
Edge cases: empty list, single node, and list with two nodes.
Pointer manipulation details: saving next node before changing links.
Recursive base case and the step where head.next.next = head and head.next = null.
Trade-offs: iterative avoids stack overflow, recursive is more elegant but less safe for large lists.
Potential follow-up: reverse in groups of k or reverse a sublist.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.