Lecture 196:-  Let's Code Reversing a Linked List

Let's implement a function to reverse a linked list iteratively in Python. We'll define a Node class representing the nodes of the linked list and a LinkedList class to manage the linked list and perform the reverse operation.

pythonCopy code

class Node:    def __init__(self, data):        self.data = data        self.next = None class LinkedList:    def __init__(self):        self.head = None    def append(self, data):        new_node = Node(data)        if not self.head:            self.head = new_node        else:            current_node = self.head            while current_node.next:                current_node = current_node.next            current_node.next = new_node    def display(self):        current_node = self.head        while current_node:            print(current_node.data, end=" -> ")            current_node = current_node.next        print("None")    def reverse(self):        prev_node = None        current_node = self.head        while current_node:            next_node = current_node.next            current_node.next = prev_node            prev_node = current_node            current_node = next_node        self.head = prev_node # Example usage: linked_list = LinkedList() linked_list.append(1) linked_list.append(2) linked_list.append(3) linked_list.append(4) print("Original Linked List:") linked_list.display()  # Output: 1 -> 2 -> 3 -> 4 -> None linked_list.reverse() print("Reversed Linked List:") linked_list.display()  # Output: 4 -> 3 -> 2 -> 1 -> None

In this implementation, the reverse function iteratively reverses the linked list. It uses three pointers (prev_node, current_node, and next_node) to keep track of the current node, the previous node, and the next node while traversing the linked list. By reversing the pointers between nodes, we effectively reverse the linked list.

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list, as we traverse each node once.

This iterative approach is efficient and preferred for reversing linked lists, especially when dealing with long lists. However, the recursive approach we discussed earlier is also useful for learning and understanding recursion concepts.