Reverse a Linked List

Problem Statement

Given the head of a singly linked list, your task is to reverse the linked list and return the new head.

Example:

Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 5 -> 4 -> 3 -> 2 -> 1

Notes:

The linked list may have any number of nodes.
You can reverse it in-place or using extra space, depending on the approach.

Approach 1: Iterative Method

The iterative approach uses three pointers: prev, curr, and nextNode. At each step:

Store curr.next in nextNode.
Reverse the link: curr.next = prev.
Move the pointers forward: prev = curr, curr = nextNode.
Repeat until curr becomes None.
Return prev as the new head.

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

def reverseList(head):
prev, curr = None, head
while curr:
nextNode = curr.next
curr.next = prev
prev = curr
curr = nextNode
return prev

def printList(node):
while node:
print(node.data, end="")
if node.next:
print(" -> ", end="")
node = node.next
print()

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)

Output:
5 -> 4 -> 3 -> 2 -> 1

Approach 2: Recursive Method

The recursive approach works by:

Recursively reaching the last node of the list.
Making each node point back to its previous node as the recursion returns.
Returning the new head of the reversed list.

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

Approach 3: Using a Stack

The stack approach involves:

Traversing the linked list and pushing all nodes onto a stack.
Popping nodes from the stack and linking them in reverse order.
Returning the new head.
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

Comparison of Approaches

Iterative: O(n) time, O(1) space – most efficient.
Recursive: O(n) time, O(n) space – uses call stack.
Stack: O(n) time, O(n) space – easy to use.