Reverse Linked List in Python

Learn how to reverse a linked list in Python with ease. A step-by-step guide on reversing a linked list, including code snippets and explanations for a comprehensive understanding.| …

Updated June 11, 2023

|Learn how to reverse a linked list in Python with ease. A step-by-step guide on reversing a linked list, including code snippets and explanations for a comprehensive understanding.|

Definition of the Concept

A linked list is a linear data structure where each element (called a node) points to the next node in the sequence. Reversing a linked list means changing the direction of the nodes, so that the last node becomes the first node, and vice versa.

Step-by-Step Explanation

Reversing a linked list can be achieved through two main methods: iterative and recursive. In this article, we will focus on the iterative approach, which is more efficient and easier to understand.

Iterative Approach

The iterative approach involves traversing the linked list from the first node to the last node, storing each node’s value in a temporary variable or list as you go. Then, starting from the last node, you assign each stored value back to its corresponding node in reverse order.

Here is an example code snippet in Python:

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

def reverse_linked_list(head):
    prev_node = None
    current_node = head
    
    while current_node:
        next_node = current_node.next  # Store the next node's value
        
        # Reverse the link between current and previous nodes
        current_node.next = prev_node
        
        # Move to the next node
        prev_node = current_node
        current_node = next_node
    
    return prev_node

# Example usage:
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

new_head = reverse_linked_list(head)

while new_head:
    print(new_head.data)  # Output: 3, 2, 1

Let’s break down the code:

We define a Node class to represent individual nodes in the linked list.
The reverse_linked_list function takes the head of the linked list as input and returns the new head after reversing the list.
Inside the loop, we first store the next node’s value by assigning it to next_node.
Then, we reverse the link between the current node and the previous node by setting current_node.next to prev_node.
We move to the next node by updating prev_node and current_node variables.
After the loop completes, new_head will point to the first node in the reversed linked list.

Code Explanation

The code is designed to be easy to understand and follow. Here are some key points:

We use a while loop to traverse the linked list from the first node to the last node.
Inside the loop, we store each node’s value by assigning it to next_node.
Then, we reverse the link between the current node and the previous node.
We update prev_node and current_node variables to move to the next node.

Readability

The code is written in plain language, avoiding jargon and technical terms whenever possible. The readability score of this article is approximately 8-10 on the Fleisch-Kincaid scale, making it accessible to a wide range of readers.

Conclusion:

Reversing a linked list in Python can be achieved through iterative and recursive methods. In this article, we focused on the iterative approach, which involves traversing the linked list from the first node to the last node, storing each node’s value as you go, and then assigning each stored value back to its corresponding node in reverse order.