Vansh Aggarwal

Posted on Apr 18

LeetCode Solution: 206. Reverse Linked List

#leetcode #dsa #programming #tutorial

Unraveling the Mystery: How to Reverse a Linked List Like a Pro! (LeetCode 206)

Hey fellow coders and aspiring problem-solvers! 👋 Vansh here, ready to dive into another classic LeetCode problem that's super fundamental for mastering linked lists: Reversing a Linked List.

This problem might seem intimidating at first glance, but I promise you, with the right approach and a little visualization, you'll be conquering it in no time. It's a fantastic exercise that builds your intuition for pointer manipulation – a crucial skill in data structures!

The Problem: 206. Reverse Linked List

Imagine you have a series of connected nodes, like a train where each car only knows which car comes next. Your task is to literally turn that train around, so the last car becomes the first, and all the connections point in the opposite direction!

Given: The head of a singly linked list.
Task: Reverse the list and return the new head.

Let's look at some examples:

Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
(The train 1 -> 2 -> 3 -> 4 -> 5 becomes 5 -> 4 -> 3 -> 2 -> 1)

Example 2:
Input: head = [1,2]
Output: [2,1]

Example 3:
Input: head = []
Output: []
(An empty list remains an empty list!)

Constraints to keep in mind:

The list can have anywhere from 0 to 5000 nodes.
Node values are between -5000 and 5000.

The "Aha!" Moment: Intuition

So, how do we flip these connections? A single linked list node only knows its next neighbor. If we simply change curr->next to point to prev, we've lost our way to the original next node! It's like cutting the rope before you've tied a new one – disaster!

The key insight is that we need to keep track of three things at any given point:

The previous node (which is already reversed or NULL initially).
The current node (the one we are currently reversing its next pointer).
The forward (or next) node (the node after current that we need to move to next, before current->next gets changed).

Think of it as a three-pointer dance: prev, curr, forward. We use forward to "save" the path, then curr dances with prev to reverse its link, and finally, prev and curr move forward to the next pair.

The Approach: Step-by-Step Iteration

We'll use an iterative approach with our three trusty pointers.

Initialization:
- prev: Initialize to NULL. This pointer will keep track of the head of our reversed sublist. When we start, there's no reversed sublist yet.
- curr: Initialize to head. This pointer will iterate through the original list, node by node.
The Loop (While curr is not NULL):
We'll continue this process until curr goes past the end of the list (meaning curr becomes NULL).

Inside each iteration:
- Step 1: Save the forward node: Before we change curr->next, we must store a reference to the node that curr is currently pointing to. ListNode* forward = curr->next; (This is our lifeline to the rest of the un-reversed list!)

*   **Step 2: Reverse the current node's pointer:**
    Now that `forward` has safely stored the next original node, we can point `curr->next` backwards, to `prev`.
    `curr->next = prev;`

*   **Step 3: Move `prev` forward:**
    The `current` node has now been successfully reversed and added to our reversed segment. So, `prev` should now become `curr`.
    `prev = curr;`

*   **Step 4: Move `curr` forward:**
    Finally, advance `curr` to the `forward` node we saved in Step 1, so we can process the next node in the original list.
    `curr = forward;`

Return: Once the loop finishes, curr will be NULL, meaning we've processed all nodes. The prev pointer will be pointing to the very last node of the original list, which is now the head of our reversed list! return prev;

Let's trace [1,2,3] visually:

Initial: prev = NULL, curr = 1 -> 2 -> 3 -> NULL

Iteration 1 (curr = 1):

forward = 2 (save 1's original next)
1->next = NULL (reverse 1's pointer)
prev = 1
curr = 2 State: NULL <- 1, prev = 1, curr = 2 -> 3 -> NULL, forward = 2

Iteration 2 (curr = 2):

forward = 3 (save 2's original next)
2->next = 1 (reverse 2's pointer)
prev = 2
curr = 3 State: NULL <- 1 <- 2, prev = 2, curr = 3 -> NULL, forward = 3

Iteration 3 (curr = 3):

forward = NULL (save 3's original next)
3->next = 2 (reverse 3's pointer)
prev = 3
curr = NULL State: NULL <- 1 <- 2 <- 3, prev = 3, curr = NULL, forward = NULL

Loop Ends.

Return prev, which is 3. The reversed list is 3 -> 2 -> 1 -> NULL. Perfect!

The Code

Here's the C++ implementation of the iterative approach:

/**
 * 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 eventually be the new head of the reversed list.
        // Initially, there's nothing before our current head, so it's NULL.
        ListNode* prev = NULL;

        // 'curr' is the pointer that iterates through the original list.
        ListNode* curr = head;

        // Loop until 'curr' has traversed the entire list.
        while (curr != NULL) {
            // Step 1: Store the next node in 'forward' before modifying curr->next.
            // This is crucial to avoid losing the rest of the list.
            ListNode* forward = curr->next;

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

            // Step 3: Move 'prev' one step forward.
            // The current node 'curr' is now part of the reversed list, so it becomes the new 'prev'.
            prev = curr;

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

        // When the loop finishes, 'curr' is NULL, and 'prev' is pointing to the
        // last node of the original list, which is now the head of the reversed list.
        return prev;
    }
};

Complexity Analysis

Time Complexity: O(N)
We traverse the linked list exactly once. For a list with N nodes, we perform a constant amount of work for each node (saving next, reversing the pointer, and advancing pointers). Thus, the time complexity scales linearly with the number of nodes.
Space Complexity: O(1)
We only use a few extra pointers (prev, curr, forward), regardless of the size of the input list. These pointers take up a constant amount of memory. Therefore, the space complexity is constant.

Key Takeaways

Three-Pointer Technique: This problem beautifully illustrates the power of using multiple pointers (prev, curr, forward) to safely manipulate linked list structures without losing track of essential references.
Saving curr->next is CRITICAL: Always remember to store the next pointer before you modify curr->next. Otherwise, you'll lose your path to the rest of the list.
Iterative vs. Recursive: While we focused on the iterative solution here (which is often preferred for its O(1) space complexity), this problem also has a elegant recursive solution! Exploring both helps deepen your understanding of linked list traversal and manipulation.
Foundation for Harder Problems: Mastering linked list reversal is a cornerstone. Many more complex linked list problems build upon this fundamental operation.

This problem is a rite of passage for anyone learning about data structures. Practice it, understand it, and you'll feel much more confident tackling linked lists!

Happy coding! ✨

Authored by Vansh2710 | Published: 2026-04-19 00:54:11

DEV Community