206. Reverse Linked List - Leetcode Solution

Leetcode Problem Link Code Solution Link:

💡 Step-by-Step Thought Process

Understand the problem: Reverse a singly linked list and return the new head.
Initialize a pointer cur to head and prev to None.
While cur is not None:
- Store cur.next in temp to preserve the next node.
- Set cur.next to prev to reverse the link.
- Move prev to cur and cur to temp to advance the pointers.
Return prev as the new head of the reversed list.

Code Solution

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        prev = None
        
        while cur:
            temp = cur.next
            cur.next = prev
            prev = cur
            cur = temp
        
        return prev

# Time Complexity: O(n)
# Space Complexity: O(1)

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;

        while (cur != nullptr) {
            ListNode* temp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = temp;
        }

        return prev;
    }
};

public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }

        return prev;
    }
}

function reverseList(head) {
    let prev = null;
    let cur = head;

    while (cur !== null) {
        let temp = cur.next;
        cur.next = prev;
        prev = cur;
        cur = temp;
    }

    return prev;
}

Detailed Explanation

Understanding the Problem: Reverse Linked List

The “Reverse Linked List” problem asks us to reverse a singly linked list, so that the head becomes the tail, and all the links point in the opposite direction. This is a foundational problem in data structures, especially for understanding pointer manipulation in linked lists.

Example:

Input: 1 → 2 → 3 → 4 → 5 → NULL
Output: 5 → 4 → 3 → 2 → 1 → NULL

Why This Problem Matters

Reversing a linked list is one of the most common operations you may need to perform in both academic and real-world applications. It teaches the fundamentals of:

In-place data structure manipulation
Understanding of pointers and memory references
Iterative and recursive control flow

Optimal Approach: Iterative Reversal

We can reverse a singly linked list using an iterative approach by keeping track of three pointers:

prev: initially set to None
cur: the current node being processed
temp: stores the next node so we don't lose reference during reversal

Steps:

Set cur = head and prev = None.
While cur is not None:
- Store cur.next in a temporary variable temp.
- Set cur.next = prev to reverse the direction of the link.
- Move prev to cur.
- Move cur to temp.
When the loop ends, prev will point to the new head of the reversed list.
Return prev.

Example Walkthrough

Input: 1 → 2 → 3
Steps:

cur = 1, temp = 2, reverse link → 1 → None, move prev = 1, cur = 2
cur = 2, temp = 3, reverse link → 2 → 1, move prev = 2, cur = 3
cur = 3, temp = None, reverse link → 3 → 2, move prev = 3, cur = None
Return prev = 3 → 2 → 1

Time and Space Complexity

Time Complexity: O(n), where n is the number of nodes. Each node is visited once.
Space Complexity: O(1), as the reversal is done in-place using constant extra space.

Edge Cases to Consider

Empty list → return None
Single-node list → return the node itself
Already reversed list → still works correctly due to uniform logic

Conclusion

The “Reverse Linked List” problem is a staple in learning linked lists and pointer manipulation. It teaches how to carefully update node references to reverse the list efficiently in-place, and builds foundational skills for more complex linked list operations.

Get Personalized Support at AlgoMap Bootcamp 💡

AlgoMap.io

Want Help Cracking FAANG?