Reverse a Linked List in Python

Problem

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

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

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

Approaches

1. Iterative Method (O(n) Time, O(1) Space)
   Use three pointers: prev, curr, next.
   Traverse the list and reverse the links step by step.
   Very efficient and commonly used.

2. Recursive Method (O(n) Time, O(n) Space)
   Recursively move to the last node.
   As recursion returns, reverse each link one by one.
   Simple to implement but uses extra call stack space.

3. Using Stack (O(n) Time, O(n) Space)
   Push all nodes into a stack.
   Pop nodes one by one to reverse the order.
   Easy to understand but uses extra memory.

Approach 1: Iterative Method (O(n) Time, O(1) Space)

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

def reverseList(head):
prev = None
curr = 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 (O(n) Time, O(n) Space)

def reverseListRecursive(head):
if not head or not head.next:
return head
rest = reverseListRecursive(head.next)
head.next.next = head
head.next = None
return rest

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 = reverseListRecursive(head)
printList(head)

Output:

5 -> 4 -> 3 -> 2 -> 1

Approach 3: Using Stack (O(n) Time, O(n) Space)

def reverseListStack(head):
stack = []
temp = head

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

head = temp
while stack:
    temp.next = stack.pop()
    temp = temp.next
temp.next = None
return head

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 = reverseListStack(head)
printList(head)

Output:

5 -> 4 -> 3 -> 2 -> 1