Python: Reverse a Linked List

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

1. Introduction

Reversing a linked list is a foundational problem in data structures. The process involves changing the next pointers of every node in the linked list to point to its previous node. It's an essential concept, often used in coding interviews and algorithm development.

2. Program Overview

The Python program provided will:

1. Define a Node class for creating linked list nodes.

2. Define a LinkedList class that will have methods for adding elements and reversing the linked list.

3. Implement the reversing technique by iterative method.

3. Code Program

class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def append(self, data): """Add a new node at the end of the linked list.""" new_node = Node(data) if not self.head: self.head = new_node return last_node = self.head while last_node.next: last_node = last_node.next last_node.next = new_node def print_list(self): """Print all elements of the linked list.""" cur_node = self.head while cur_node: print(cur_node.data, end=" -> ") cur_node = cur_node.next print("None") def reverse(self): """Reverse the linked list.""" prev = None current = self.head while current: nxt = current.next current.next = prev prev = current current = nxt self.head = prev # Sample test llist = LinkedList() llist.append(1) llist.append(2) llist.append(3) llist.append(4) print("Original Linked List:") llist.print_list() llist.reverse() print("\nReversed Linked List:") llist.print_list() 

Output:

Original Linked List: 1 -> 2 -> 3 -> 4 -> None Reversed Linked List: 4 -> 3 -> 2 -> 1 -> None 

4. Step By Step Explanation

1. We start by defining a Node class, which is a basic building block of the linked list.

2. The LinkedList class has an append method to add new nodes to the list and a print_list method to display the list.

3. The reverse method inside the LinkedList class is where the magic happens. Here's a step-by-step breakdown of the reversing process:

• We initialize three pointers: prev, current, and nxt. Initially, prev is set to None because the last node in the reversed list will point to None.
• We traverse the linked list using the current pointer.
• During each iteration, we first save the next node using the nxt pointer.
• We then change the next pointer of the current node to point to prev.
• We move the prev and current pointers one step forward.
• Once the traversal is complete, we set the head of the linked list to the prev pointer, effectively reversing the list.