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

def reverse_linked_list(head):
    previous = None
    current = head
    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))))
new_head = reverse_linked_list(head)
while new_head:
    print(new_head.value, end=" -> " if new_head.next else "")
    new_head = new_head.next

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

def reverse_linked_list_recursive(current, previous=None):
    if not current:
        return previous
    next_node = current.next
    current.next = previous
    return reverse_linked_list_recursive(next_node, current)

# Example Usage:
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
new_head = reverse_linked_list_recursive(head)
while new_head:
    print(new_head.value, end=" -> " if new_head.next else "")
    new_head = new_head.next

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

def reverse_linked_list_stack(head):
    stack = []
    current = head
    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
    return new_head

# Example Usage:
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
new_head = reverse_linked_list_stack(head)
while new_head:
    print(new_head.value, end=" -> " if new_head.next else "")
    new_head = new_head.next

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

def reverse_linked_list_pythonic(head):
    previous, current = None, head
    while current:
        current.next, previous, current = previous, current, current.next
        
    return previous

# Example Usage:
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
new_head = reverse_linked_list_pythonic(head)
while new_head:
    print(new_head.value, end=" -> " if new_head.next else "")
    new_head = new_head.next

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

def reverse_linked_list_oneliner(head):
    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))))
print(reverse_linked_list_oneliner(head))

Output: [4, 3, 2, 1]

This code example is not for a proper linked list reversal but demonstrates how a linked list’s values can be reversed in a list format using a Python one-liner. The list comprehension and slicing reverse the values, but additional steps are required to reconstruct an actual linked list.

Summary/Discussion

  • Method 1: Iterative Approach. Highly efficient and straightforward in place reversal. Can be confusing for beginners with multiple pointers.
  • Method 2: Recursive Approach. A more elegant solution that can be easier to understand. Risks stack overflow for very large lists due to recursive calls.
  • Method 3: Using a Stack. Intuitive concept leveraging LIFO. Involves extra memory usage as opposed to in-place methods.
  • Method 4: In-Place Reversal with Pythonic Syntax. Iterative approach with concise syntax. Requires understanding of advanced Python features.
  • Method 5: Using List Comprehension. Offers quick reversal of values but not applicable to linked lists directly. Additional steps required for full reversal.