LeetCode Solution: 206. Reverse Linked List

Conquering Linked Lists: How to Reverse Them Like a Pro (LeetCode 206 Deep Dive)

Hey awesome developers! 👋 Ever stared at a data structure problem and felt a little intimidated? You're not alone! Today, we're going to tackle a classic LeetCode problem, "206. Reverse Linked List", in a super beginner-friendly way.

This problem is a rite of passage for anyone learning about linked lists. It teaches fundamental pointer manipulation, which is a core skill in computer science. Ready to level up your linked list game? Let's dive in!

The Problem: Reverse Linked List

Imagine you have a train, but instead of connecting cars from front to back, they're connected from back to front! That's essentially what reversing a linked list is about.

You're given the head of a singly linked list. Your task is to reverse all the connections (pointers) so that the last node becomes the new head, and the original head becomes the last node. Then, return the new head of this reversed list.

What's a Linked List?
Think of it like a scavenger hunt. Each clue (node) tells you where to find the next clue.

• Each Node has a value (the actual data, like a number).
• Each Node also has a next pointer, which points to the next node in the sequence.
• The head is where the list starts.
• The last node's next pointer usually points to NULL (or nullptr in C++), signifying the end.

Let's look at the examples:

Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Initially: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
After reversing: NULL <- 1 <- 2 <- 3 <- 4 <- 5 (which we read as 5 -> 4 -> 3 -> 2 -> 1 -> NULL)

Example 2:
Input: head = [1,2]
Output: [2,1]
Initially: 1 -> 2 -> NULL
After reversing: NULL <- 1 <- 2 (read as 2 -> 1 -> NULL)

Example 3:
Input: head = []
Output: []
If there's no list, there's nothing to reverse! Simple enough.

Constraints:

• The list can have between 0 and 5000 nodes.
• Node values are between -5000 and 5000.

Intuition: The "Three Pointer Trick"

How do we even start reversing pointers without losing track of the rest of the list? Imagine you're holding a rope, and you want to tie it in reverse. You can't just untie one knot and retie it without holding onto the next piece, right?

The key insight for reversing a linked list iteratively is to use three pointers:

1. prev: This pointer keeps track of the node before the current one. This is crucial because it's where the current node's next pointer will eventually point after reversal. It starts as NULL because the first node's next will point to nothing (it becomes the new tail).
2. curr: This pointer is our main traveler, iterating through the list. It points to the node we are currently looking at and whose next pointer we are about to reverse. It starts at head.
3. forward (or next_node): This pointer temporarily stores the next node before we modify curr->next. Without this, once we point curr->next to prev, we'd lose our way to the rest of the original list!

At each step, we'll perform these actions:

1. Save the next node: Store curr->next in forward.
2. Reverse the link: Point curr->next to prev.
3. Move prev forward: Update prev to curr.
4. Move curr forward: Update curr to forward (the node we saved earlier).

Repeat until curr becomes NULL, meaning we've processed all nodes.

The Approach: Step-by-Step Iteration

Let's walk through an example: 1 -> 2 -> 3 -> NULL

1. Initialization:

   • prev = NULL
   • curr = head (points to 1)
   • forward = NULL (will be used inside the loop)

   Diagram:
   NULL <- prev
1 -> 2 -> 3 -> NULL
^curr

2. First Iteration (while curr is not NULL):

   • curr is 1.
   • forward = curr->next; ( forward points to 2)
   • curr->next = prev; (1->next now points to NULL. List: NULL <- 1)
   • prev = curr; (prev now points to 1)
   • curr = forward; (curr now points to 2)

   Diagram:
   NULL <- 1 <- prev
2 -> 3 -> NULL
^curr
^forward (old position)

3. Second Iteration (while curr is not NULL):

   • curr is 2.
   • forward = curr->next; (forward points to 3)
   • curr->next = prev; (2->next now points to 1. List: NULL <- 1 <- 2)
   • prev = curr; (prev now points to 2)
   • curr = forward; (curr now points to 3)

   Diagram:
   NULL <- 1 <- 2 <- prev
3 -> NULL
^curr
^forward (old position)

4. Third Iteration (while curr is not NULL):

   • curr is 3.
   • forward = curr->next; (forward points to NULL)
   • curr->next = prev; (3->next now points to 2. List: NULL <- 1 <- 2 <- 3)
   • prev = curr; (prev now points to 3)
   • curr = forward; (curr now points to NULL)

   Diagram:
   NULL <- 1 <- 2 <- 3 <- prev
NULL
^curr
^forward (old position)

5. Loop Termination:

   • curr is now NULL. The loop condition curr != NULL is false, so the loop ends.

6. Return:

   • We return prev. At this point, prev points to 3, which is the new head of our reversed list: 3 -> 2 -> 1 -> NULL.

And just like that, the list is reversed!

The Code

Here's the C++ implementation for the iterative approach.
(LeetCode uses a ListNode struct, typically defined as follows):

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 'prev' will be used to build the new reversed list.
        // It starts as NULL because the first node of the original list
        // will become the last node, pointing to NULL.
        ListNode* prev = nullptr;

        // 'curr' is our main pointer, traversing the original list.
        // It starts at the head.
        ListNode* curr = head;

        // Loop until 'curr' reaches the end of the original list (becomes NULL).
        while (curr != nullptr) {
            // 1. Store the next node in 'forward'.
            // This is crucial to not lose the rest of the list after we modify curr->next.
            ListNode* forward = curr->next;

            // 2. Reverse the current node's pointer:
            // Make 'curr->next' point to 'prev'.
            curr->next = prev;

            // 3. Move 'prev' one step forward:
            // The current node (curr) is now reversed, so it becomes the new 'prev'
            // for the next iteration.
            prev = curr;

            // 4. Move 'curr' one step forward:
            // Advance 'curr' to the node we saved in 'forward'.
            curr = forward;
        }

        // After the loop, 'prev' will be pointing to the new head of the reversed list.
        // 'curr' will be NULL.
        return prev;
    }
};

Time & Space Complexity Analysis

• Time Complexity: O(N)
  We traverse the linked list exactly once. For each node, we perform a constant number of operations (pointer assignments). If there are 'N' nodes in the list, the time taken is directly proportional to 'N'.

• Space Complexity: O(1)
  We only use a few extra pointers (prev, curr, forward) regardless of the number of nodes in the list. These pointers take up a constant amount of space, hence O(1). This is super efficient!

Key Takeaways

1. Linked List Reversal is Fundamental: Mastering this problem is key to understanding pointer manipulation in linked lists, a skill that's transferable to many other data structure problems.
2. The Three-Pointer Technique: The prev, curr, forward (or next_node) pattern is incredibly powerful and common for iterative linked list operations where you need to modify links.
3. Visualizing Helps: Drawing out the pointers and their movements for a small example (like 1 -> 2 -> 3) is invaluable for debugging and understanding the logic.
4. Edge Cases: Always consider empty lists ([]) and single-node lists ([1]). Our solution handles these correctly! If head is NULL, curr is NULL, the loop doesn't run, and prev (which is NULL) is returned, which is correct. If head is [1], the loop runs once, prev becomes 1, and curr becomes NULL, returning 1.

This problem also has an elegant recursive solution (a "follow-up" hint from LeetCode!). While we focused on the iterative approach today, exploring the recursive one would be another fantastic learning experience!

Keep practicing, keep coding, and see you in the next one!

---

Authored by: Vansh2710
Published on: 2026-04-14 23:22:36