5 Best Ways to Display Linked List Nodes in Reverse in Python

by

💡 Problem Formulation: This article addresses the scenario where we have a singly linked list containing a series of nodes with integer values. The goal is to display the values of these nodes in reverse order. For instance, given a linked list 1 -> 2 -> 3 -> 4, the desired output is 4 -> 3 -> 2 -> 1, without utilizing recursion.

Method 1: Iterative Approach with Stack

A common non-recursive technique involves utilizing a stack to reverse the node sequence in a singly linked list. Stacks follow the Last-In-First-Out (LIFO) principle, which is perfect for this use case. As we traverse the list, we push each node’s value onto the stack. Afterwards, we pop the values from the stack, which results in a reversed order of the list’s elements.

Here’s an example:

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

def reverse_linked_list(head):
    stack = []
    current = head
    while current:
        stack.append(current.value)
        current = current.next
    while stack:
        print(stack.pop())

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

The output of this code snippet:

4
3
2
1

This code defines a ListNode class that represents each node of the linked list and a reverse_linked_list function that prints the list’s values in reverse using a stack.

Method 2: Iterative Approach with List

By leveraging Python’s list data structure, we can achieve the same end result as with a stack, but with potentially more efficient list operations. We iterate through the linked list, collecting the values in a list, and then reverse the list using the built-in reverse method or slicing.

Here’s an example:

class ListNode:
    # ... (Same as above)

def reverse_linked_list(head):
    values = []
    current = head
    while current:
        values.append(current.value)
        current = current.next
    for value in values[::-1]:
        print(value)

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

The output of this code snippet:

4
3
2
1

The reverse_linked_list function collects node values in a list and then prints those values in reverse by iterating over the list in reverse order using slicing.

Method 3: Iterative In-Place Reversal

In some situations, instead of printing the reversed nodes, you may want to modify the linked list in-place to reverse its direction. This approach manipulates the node pointers themselves, reversing the list without additional storage, and thus saving space.

Here’s an example:

class ListNode:
    # ... (Same as above)

def reverse_linked_list(head):
    prev = None
    current = head
    while current:
        next_temp = current.next
        current.next = prev
        prev = current
        current = next_temp
    while prev:
        print(prev.value)
        prev = prev.next

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

The output of this code snippet:

4
3
2
1

This method modifies the original linked list by reversing the direction of the links between nodes. After reversing, it traverses the modified list to print the values.

Method 4: Using Iterable Unpacking

Python’s powerful iterable unpacking can be used when converting the linked list to a list of values. By converting the linked list to a list and unpacking it in reverse order, we can print each value on a new line.

Here’s an example:

class ListNode:
    # ... (Same as above)

def reverse_linked_list(head):
    values = []
    current = head
    while current:
        values.append(current.value)
        current = current.next
    print(*values[::-1], sep='\n')

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

The output of this code snippet:

4
3
2
1

This code accumulates node values into a list and then unpacks the list in reverse order using Python’s asterisk notation, with each value printed on a separate line.

Bonus One-Liner Method 5: Reverse Iterator

For smaller linked lists or when performance isn’t critical, a one-liner that combines list comprehension with the Python built-in function reversed() provides an elegant solution.

Here’s an example:

class ListNode:
    # ... (Same as above)

def reverse_linked_list(head):
    print(*reversed([node.value for node in iter_list(head)]), sep='\n')

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

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

The output of this code snippet:

4
3
2
1

Using a convenient helper generator, iter_list, this example creates a list of nodes and then prints them in reverse with the reversed function.

Summary/Discussion

  • Method 1: Iterative Approach with Stack. Utilizes the LIFO nature of a stack to reverse the node sequence. Robust and easy to understand, but uses extra memory for the stack.
  • Method 2: Iterative Approach with List. Employs Python’s list and slicing to reverse the node sequence. Memory overhead similar to Method 1, but potentially faster due to list optimizations.
  • Method 3: Iterative In-Place Reversal. Modifies the list in-place, saving space. While efficient, it alters the original data structure, which may not be desired in all cases.
  • Method 4: Using Iterable Unpacking. Uses Python’s iterable unpacking to print the reversed list in a concise manner. Elegant and compact, but the efficiency is similar to Method 2.
  • Bonus Method 5: Reverse Iterator. Offers a compact one-liner using a generator and the reversed function. Simplicity at the cost of performance; best for less demanding applications.