29. Reverse Linked List
easyAsked at DatadogReverse a singly linked list. Datadog uses this as the bedrock linked-list question — pointer manipulation here is required for harder problems like reverse-in-groups or merge-k-sorted.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Datadog loops.
- Glassdoor (2026-Q1)— Datadog phone screen — used to filter on pointer manipulation.
- Blind (2025-12)— Recurring Datadog warmup.
Problem
Given the head of a singly linked list, reverse the list, and return the reversed list.
Constraints
The number of nodes in the list is the range [0, 5000].-5000 <= Node.val <= 5000
Examples
Example 1
head = [1,2,3,4,5][5,4,3,2,1]Example 2
head = [1,2][2,1]Example 3
head = [][]Approaches
1. Collect to array + rebuild
Dump values to array, build a new list from the end.
- Time
- O(n)
- Space
- O(n)
function reverseList(head) {
const vals = [];
while (head) { vals.push(head.val); head = head.next; }
const dummy = { val: 0, next: null };
let tail = dummy;
for (let i = vals.length - 1; i >= 0; i--) {
tail.next = { val: vals[i], next: null };
tail = tail.next;
}
return dummy.next;
}Tradeoff: O(n) extra memory + allocation. Datadog will fail this for not doing in-place pointer reversal.
2. Iterative three-pointer (optimal)
Walk forward with prev, curr, next. At each step: save next, flip curr.next to prev, advance.
- Time
- O(n)
- Space
- O(1)
function reverseList(head) {
let prev = null;
let curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}Tradeoff: O(1) extra space, single pass. The save-flip-advance idiom is the foundation for harder Datadog linked-list problems.
Datadog-specific tips
Datadog interviewers will follow up with: 'Now reverse in groups of K' or 'Now reverse a sublist between m and n.' Show that the three-pointer idiom generalizes — every harder linked-list question builds on it. Mention the recursive version too; both should be in your toolkit.
Common mistakes
- Forgetting to save curr.next BEFORE reassigning it — loses the rest of the list.
- Returning head at the end — head is now the tail; return prev (the new head).
- Recursive version with O(n) stack — works but blows up on long lists in JS.
Follow-up questions
An interviewer at Datadog may pivot to one of these next:
- Reverse Linked List II (LC 92) — reverse between positions m and n.
- Reverse Nodes in K-Group (LC 25) — generalization.
- Palindrome Linked List (LC 234) — uses reverse-second-half as a subroutine.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Recursive or iterative?
Iterative is preferred — O(1) space vs O(n) recursion stack. The recursive form is elegant but doesn't survive 10K+ length lists in JS.
Why save next BEFORE reassigning?
curr.next = prev overwrites curr.next, so if you didn't save it first, you've lost your way to the rest of the list.