Reverse a Linked List

Reverse a Linked List
Introduction

A Linked List is a linear data structure where each element (node) contains:

Data

Pointer to the next node

Reversing a linked list means changing the direction of the links so that the last node becomes the first node.

Example:

Original: 1 -> 2 -> 3 -> 4 -> 5
Reversed: 5 -> 4 -> 3 -> 2 -> 1
Approach 1: Iterative Method (Most Efficient)
Idea

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

prev

curr

next

At each step:

Store next node

Reverse the current pointer

Move all pointers forward

Steps

Initialize:

prev = None

curr = head

Traverse the list

Store next node

Reverse link (curr.next = prev)

Move prev and curr forward

Continue until curr becomes None

prev will be the new head

Python Code
class Node:
def init(self, data):
self.data = data
self.next = None

def reverseList(head):
prev = None
curr = head

while curr is not None:
    nextNode = curr.next
    curr.next = prev
    prev = curr
    curr = nextNode

return prev

def printList(head):
temp = head
while temp:
print(temp.data, end=" -> ")
temp = temp.next
print("None")

Creating Linked List

head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)

head = reverseList(head)
printList(head)
Complexity
Time Space
O(n) O(1)

This is the best method.

Approach 2: Recursion Method
Idea

We recursively go to the last node, then reverse the links while returning back.

Steps

Reach last node using recursion

Make next node point to current node

Set current.next = None

Return new head

Python Code
def reverseList(head):
if head is None or head.next is None:
return head

rest = reverseList(head.next)
head.next.next = head
head.next = None

return rest

Complexity
Time Space
O(n) O(n)

Space is O(n) because of recursion stack.

Approach 3: Using Stack
Idea

Push all nodes into a stack and then pop them to reverse the list.

Python Code
def reverseList(head):
stack = []
temp = head

while temp:
    stack.append(temp)
    temp = temp.next

head = stack.pop()
temp = head

while stack:
    temp.next = stack.pop()
    temp = temp.next

temp.next = None
return head

Complexity
Time Space
O(n) O(n)
Comparison of Methods
Method Time Space
Iterative O(n) O(1)
Recursion O(n) O(n)
Stack O(n) O(n)

Best Method → Iterative Method

Conclusion

Reversing a linked list is a very important problem in data structures.

Key concepts learned:

Pointer manipulation

Linked list traversal

Recursion

Stack usage

In-place reversal

The iterative method is the most efficient because it uses O(1) space.