Log inSign up
easyLeetCodeNot Started

Reverse Linked List

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

Given the head of a singly linked list, reverse the list, and return *the reversed list*.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Explanation: Pointers are inverted so the list traverses from 5 back to 1.

Example 2:

Input: head = [1,2]
Output: [2,1]
Explanation: Reversed to [2,1].

Example 3:

Input: head = []
Output: []
Explanation: Empty list reversed is empty.

Constraints:

  • The number of nodes in the list is in the range [0, 5000].
  • -5000 <= Node.val <= 5000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand prev, current, and next as a moving three-part window.
  • Reverse pointers without losing access to the rest of the list.
  • Recognize why recursion naturally uses call-stack space.
  • Write an iterative O(N) linked-list reversal.
  • Trace pointer changes node by node instead of thinking only about final output.

1. Stack-Based Value / Node Extraction

Intuition

1. Traverse the linked list and push every node reference onto a stack. 2. Create a dummy head node. 3. Repeatedly pop from the stack and append each node to the end of the new chain. 4. Set the final node's next pointer to null. 5. Return dummy.next.

When to apply: Quick conceptual demonstration leveraging stack data structures.

Algorithm

  1. Push all nodes onto stack.
  2. Pop nodes sequentially and re-link.
  3. Set terminal pointer to null.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <stack>
3
4struct ListNode {
5 int val;
6 ListNode *next;
7 ListNode() : val(0), next(nullptr) {}
8 ListNode(int x) : val(x), next(nullptr) {}
9 ListNode(int x, ListNode *next) : val(x), next(next) {}
10};
11
12class Solution {
13public:
14 ListNode* reverseList(ListNode* head) {
15 if (!head || !head->next) return head;
16
17 std::stack<ListNode*> st;
18 ListNode* curr = head;
19 while (curr != nullptr) {
20 st.push(curr);
21 curr = curr->next;
22 }
23
24 ListNode dummy(0);
25 ListNode* tail = &dummy;
26 while (!st.empty()) {
27 tail->next = st.top();
28 st.pop();
29 tail = tail->next;
30 }
31 tail->next = nullptr;
32 return dummy.next;
33 }
34};
35
36int main() {
37 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
38 Solution sol;
39 ListNode* res = sol.reverseList(head);
40 while (res != nullptr) {
41 std::cout << res->val << " ";
42 res = res->next;
43 }
44 std::cout << std::endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(N) — One pass to push N nodes and one pass to pop N nodes: O(N) total.
  • Space complexity: O(N) — Stack holds references to all N nodes in memory: O(N) extra space.

2. Recursive Post-Order Reversal

Intuition

1. Base case: If head == null || head.next == null, return head. 2. Recursive call: newHead = reverseList(head.next). 3. Rewire: head.next.next = head. 4. Sever old forward pointer: head.next = null. 5. Return newHead.

When to apply: Functional and recursive problem-solving paradigms.

Algorithm

  1. Base case: return head if null or single node.
  2. Recursively call reverseList on head.next.
  3. Point next node's next back to head.
  4. Nullify head's forward link.
  5. Return reversed new head.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode() : val(0), next(nullptr) {}
7 ListNode(int x) : val(x), next(nullptr) {}
8 ListNode(int x, ListNode *next) : val(x), next(next) {}
9};
10
11class Solution {
12public:
13 ListNode* reverseList(ListNode* head) {
14 if (!head || !head->next) return head;
15
16 ListNode* newHead = reverseList(head->next);
17 head->next->next = head;
18 head->next = nullptr;
19
20 return newHead;
21 }
22};
23
24int main() {
25 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
26 Solution sol;
27 ListNode* res = sol.reverseList(head);
28 while (res != nullptr) {
29 std::cout << res->val << " ";
30 res = res->next;
31 }
32 std::cout << std::endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N) — Visits each node once going down the call stack and once returning up: O(N) operations.
  • Space complexity: O(N) recursion stack — Recursion call stack depth equals length N: O(N) memory.

3. Iterative Three-Pointer In-Place Reversal

Intuition

1. Initialize prev = null, curr = head. 2. While curr != null: - nextTemp = curr.next - curr.next = prev - prev = curr - curr = nextTemp 3. Return prev.

When to apply: The industry standard, gold-standard solution for in-place linked list reversal.

Algorithm

  1. Initialize prev = null, curr = head.
  2. While curr != null:
  3. - Save nextTemp = curr.next.
  4. - Reverse link: curr.next = prev.
  5. - Advance prev = curr.
  6. - Advance curr = nextTemp.
  7. Return prev.

Linked List Interactive Dry Run

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Node 1 is about to point to null (becoming the new tail)
Visual state
Values and pointers at this exact step
linked list
This linked list trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Why this step matters

Node 1 is about to point to null (becoming the new tail).

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode() : val(0), next(nullptr) {}
7 ListNode(int x) : val(x), next(nullptr) {}
8 ListNode(int x, ListNode *next) : val(x), next(next) {}
9};
10
11class Solution {
12public:
13 ListNode* reverseList(ListNode* head) {
14 ListNode* prev = nullptr;
15 ListNode* curr = head;
16
17 while (curr != nullptr) {
18 ListNode* nextTemp = curr->next;
19 curr->next = prev;
20 prev = curr;
21 curr = nextTemp;
22 }
23
24 return prev;
25 }
26};
27
28int main() {
29 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
30 Solution sol;
31 ListNode* res = sol.reverseList(head);
32 while (res != nullptr) {
33 std::cout << res->val << " ";
34 res = res->next;
35 }
36 std::cout << std::endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N) — Each node is visited exactly once in a single pass of length N: O(N) runtime.
  • Space complexity: O(1) auxiliary — Only 3 pointer variables are used, requiring strictly O(1) auxiliary memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Stack-Based Value / Node ExtractionO(N)O(N)Push all nodes onto an explicit LIFO stack, then pop them one by one to construct the reversed list.High time complexity
2.Recursive Post-Order ReversalO(N)O(N) recursion stackRecursively reverse the sublist starting at head.next. On return, set head.next.next = head and head.next = null.—
3.Iterative Three-Pointer In-Place ReversalOptimalO(N)O(1) auxiliaryTraverse the list using prev, curr, and nextTemp pointers, reorienting each node's next pointer to prev in O(1) auxiliary space.—

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Reassigning curr.next = prev before saving curr.next in nextTemp, severing access to the rest of the list.

Pitfall 2:

Returning curr instead of prev at the end of loop (when loop ends, curr is null and prev is the new head).

Pitfall 3:

Forgetting to set head.next = null in recursive reversal, causing a two-node cycle between head and head.next.

Crucial Edge Cases to Validate:

  • An empty list.
  • A list containing one node.
  • A list containing exactly two nodes.
  • The original head must become the final tail and point to null.
  • The next pointer must be saved before current.next is changed.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Draw the arrows before and after one iteration.
  2. Say the invariant aloud: prev is already reversed, current is the first node not yet reversed.
  3. Explain that every node is visited once, so time is O(N).
  4. Choose iterative reversal when auxiliary space should remain O(1).
Back to DSA Sheet