# 5 Best Ways to Reverse a Linked List in Python

Rate this post

π‘ Problem Formulation: Reversing a linked list is a common challenge that involves changing the direction of the pointers in a linked list so that the last node becomes the first node and vice versa. For instance, if our input is a linked list represented as 1 -> 2 -> 3 -> 4 -> NULL, the desired output after reversal would be 4 -> 3 -> 2 -> 1 -> NULL. This article presents the 5 best ways to reverse a linked list in Python.

## Method 1: Iterative Approach

This method entails traversing the linked list and reversing the pointers one by one. We will maintain three pointers: previous, current, and next. As we iterate, we’ll reverse the current node’s pointer to point to the previous node, effectively reversing the list as we go along. The process continues until all nodes have been visited and reversed.

Here’s an example:

```class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next

previous = None
while current:
next_node = current.next
current.next = previous
previous = current
current = next_node
return previous

# Example Usage:
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
```

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

In this code snippet, we define a `ListNode` class representing each node, and a function `reverse_linked_list()` which performs the iterative reversal of the linked list. By repeatedly redirecting the current node’s pointer to the previous node, we successfully reverse the linked list. The output demonstrates the linked list after being reversed using our method.

## Method 2: Recursive Approach

With recursion, we reverse the linked list by reaching the end of the list and then modifying the pointers while unwinding the stack. The base case occurs when we reach the end of the list, after which we modify the pointers from the last node backward.

Here’s an example:

```class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next

if not current:
return previous
next_node = current.next
current.next = previous

# Example Usage:
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
```

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

In this snippet, the function `reverse_linked_list_recursive()` uses recursion to reverse the linked list. We pass two parameters, the current node and the previous node, which is initialized to None. On reaching the end of the list, the last node will be returned as the new head, and the reversal occurs as the recursive calls are returned.

## Method 3: Using a Stack

This method uses a stack to collect all the nodes of the linked list and then re-creates the linked list by popping the nodes off the stack, which results in a reversed list since stacks follow the Last In, First Out (LIFO) principle.

Here’s an example:

```class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next

stack = []
while current:
stack.append(current)
current = current.next

new_head = current = stack.pop() if stack else None
while stack:
current.next = stack.pop()
current = current.next
if current:
current.next = None

# Example Usage:
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
```

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

This code uses a stack to reverse the linked list. Each node is pushed onto the stack, and then nodes are popped off and chained to form the reversed linked list. The last node processed is set to point to None to terminate the list correctly.

## Method 4: In-Place Reversal with Pythonic Syntax

This method is a variation of the iterative method but uses Python-specific syntax features like tuple unpacking to clean up the code and reduce the number of lines needed to achieve list reversal.

Here’s an example:

```class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next

while current:
current.next, previous, current = previous, current, current.next

return previous

# Example Usage:
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
```

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

The `reverse_linked_list_pythonic()` function uses Python’s tuple unpacking feature to clean up the iterative approach, making the code simpler and more readable. The logic essentially remains the same.

## Bonus One-Liner Method 5: Using List Comprehension

While not a direct method to reverse a linked list, this bonus approach first converts the linked list to a Python list using list comprehension, reverses it, and then reconstructs a new linked list from the reversed list.

Here’s an example:

```class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next

return [node.value for node in iter_list(head)][::-1]

def iter_list(node):
while node:
yield node
node = node.next

# Example Usage:
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))