How to Reverse a Linked List in Python

Did you know you can easily reverse a linked list?

Imagine a line of people holding hands, and you need to reverse their positions without breaking the chain. Reversing a linked list is somewhat similar. It might sound complex, but with the right approach, it becomes really straight forward. Let's dive into how to reverse a linked list using Python.

Why reversing a linked list matters

Reversing a linked list is a very common problem, typically in coding interviews but also in real-world applications. It helps in understanding the manipulation of pointers and can be a part of something very crucial in managing data structures.

What is a linked list?

A linked list is quite similar to other data structures, but all its elements are not kept in contiguous memory locations. The elements in a linked list are linked with each other using pointers.

Reversing a Linked List

In this section, we will learn how to reverse a linked list and at the same time practice the first way told in the introduction, i.e., reversing each link.

Step 1: Define the Nodes Structure

let's first define the structure of a node. Each node will have a data part and a reference to the next node.

1class ListNode:
2    def __init__(self, val=0, next=None):
3        self.val = val  # Store the data in the node
4        self.next = next  # Initialize the next pointer to None

Step 2: Create the linked list

Now, let’s create the linked list and add methods to append nodes and reverse the list.

1class LinkedList:
2    def __init__(self):
3        self.head = None  # Initialize the head of the list to None
4
5    # Function to add a new node at the end
6    def append(self, data):
7        new_node = ListNode(data)
8        if not self.head:
9            self.head = new_node  # If the list is empty, make the new node the head
10            return
11        last = self.head
12        while last.next:
13            last = last.next  # Traverse to the end of the list
14        last.next = new_node  # Link the new node at the end of the list
15
16    # Function to reverse the linked list
17    def reverse(self):
18        prev = None
19        current = self.head
20        while current:
21            next_node = current.next  # Store the next node
22            current.next = prev  # Reverse the current node's pointer
23            prev = current  # Move pointers one position ahead
24            current = next_node
25        self.head = prev  # Update the head to the new first node
26
27    # Function to print the linked list
28    def printList(self):
29        current = self.head
30        while current:
31            print(current.val, end=" -> ")
32            current = current.next
33        print("NULL")

Step 3: Example usage

Here’s how you can use the above functions to create a linked list, add nodes, and reverse the list.

1if __name__ == "__main__":
2    llist = LinkedList()
3    llist.append(1)
4    llist.append(2)
5    llist.append(3)
6    llist.append(4)
7    llist.append(5)
8
9    print("Original List:")
10    llist.printList()
11
12    llist.reverse()
13
14    print("Reversed List:")
15    llist.printList()

Explanation of code

• Class Definition: We start by defining a ListNode class to represent each node in the linked list.
• Linked List Implementation: The LinkedList class manages the nodes. It includes methods to append new nodes, reverse the list, and print the list.
• Appending Nodes: The append method adds new nodes to the end of the list.
• Reversing the List: The reverse method iteratively reverses the pointers of the nodes.
• Printing the List: The printList method prints the linked list.

Key points to remember

• Pointer Manipulation: Understanding how to change pointers is crucial.
• Iterative Approach: This method uses an iterative approach to reverse the list.
• Memory Management: Ensure that all nodes are correctly pointed to avoid memory leaks or broken links.

Conclusion

Reversing a linked list in Python is hence very critical for coding interviews. This will surely give you the ability to handle linked lists and reinforce your data structure knowledge. Keep in practice, and soon you'll handle your linked list in your projects like a pro!