Python Program to Reverse a linked list

Python Program to Reverse a linked list

Let's break down the problem of reversing a linked list in Python step by step.

Reversing a Linked List in Python:

1. Node Class:

First, let's define the structure for the nodes in the linked list.

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

2. LinkedList Class:

We'll define a LinkedList class that will house the functionalities like insertion and reversal.

class LinkedList: def __init__(self): self.head = None # Function to insert a new node at the beginning def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node # Function to reverse the linked list def reverse(self): prev = None current = self.head while current is not None: next_node = current.next current.next = prev prev = current current = next_node self.head = prev # Function to print the linked list def printList(self): temp = self.head while temp: print(temp.data, end=" -> ") temp = temp.next print("None")

3. Main Function:

Now, let's add a main function to test our linked list reversal code.

def main(): llist = LinkedList() llist.push(20) llist.push(4) llist.push(15) llist.push(85) print("Given Linked List:") llist.printList() llist.reverse() print("\nReversed Linked List:") llist.printList() if __name__ == "__main__": main()

Output:

Given Linked List: 85 -> 15 -> 4 -> 20 -> None Reversed Linked List: 20 -> 4 -> 15 -> 85 -> None

How it works:

  1. The Node class simply creates a new node.
  2. The LinkedList class has various functions:
    • push: Adds a new node at the beginning.
    • reverse: Reverses the linked list in-place. It uses three pointers to reverse the direction of the pointers in the linked list.
    • printList: Prints the linked list.
  3. The main function initializes the linked list, pushes some values into it, prints the initial linked list, reverses it, and then prints the reversed linked list.

The key logic in the reversal process lies in the reverse method where we change the pointers' direction in the linked list iteratively.

More Tags

windows-xp-sp3 subsequence phpunit projection sharepoint-jsom jquery insert-update where-clause sonarqube-api systemctl

More Programming Guides

Other Guides

More Programming Examples