Reverse a Linked List

Problem Statement

Given the head of a linked list, reverse the list and return the new head.

Example

Input:

1 → 2 → 3 → 4 → 5 → NULL

Output:

5 → 4 → 3 → 2 → 1 → NULL
Table of Contents
Approach – Iterative Method (O(n) Time | O(1) Space)
Alternate Approach 1 – Recursion (O(n) Time | O(n) Space)
Alternate Approach 2 – Using Stack (O(n) Time | O(n) Space)

1. Approach – Iterative Method (Most Optimal) Idea

We reverse the linked list by changing the direction of links using three pointers:

prev
curr
next_node

At each step:

Store next node.
Reverse current node’s pointer.
Move all pointers one step forward.

We repeat this until the list becomes NULL.

Step-by-Step Logic

Initial state:

prev = NULL
curr = head

While curr is not NULL:

Save next node → next_node = curr.next
Reverse link → curr.next = prev
Move prev forward → prev = curr
Move curr forward → curr = next_node

At the end:

prev becomes the new head.
Python Code (Iterative – O(1) Space)
class Solution:
def reverseList(self, head):
prev = None
curr = head

    while curr:
        next_node = curr.next   # Store next node
        curr.next = prev        # Reverse the link
        prev = curr             # Move prev forward
        curr = next_node        # Move curr forward

    return prev

Time and Space Complexity

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

Why O(1)?
Because we are only using three pointers.