This is a Python program to reverse a linked list.
Problem Description
The program creates a linked list and reverses it.
Problem Solution
1. Create a class Node with instance variables data and next.
2. Create a class LinkedList with instance variables head and last_node.
3. The variable head points to the first element in the linked list while last_node points to the last.
4. Define methods append and display.
5. The method append takes a data item as argument and appends a node with that data item to the list.
6. The method display traverses the list from the first node and prints the data of each node.
7. Define a function reverse_llist which takes a linked list as argument and reverses it.
8. The function reverse_llist iterates through the list using three pointers to reverse it.
9. Create an instance of LinkedList, reverse the list and display it.
Program/Source Code
Here is the source code of a Python program to reverse a linked list. The program output is shown below.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.last_node = None
def append(self, data):
if self.last_node is None:
self.head = Node(data)
self.last_node = self.head
else:
self.last_node.next = Node(data)
self.last_node = self.last_node.next
def display(self):
current = self.head
while current:
print(current.data, end = ‘ ‘)
current = current.next
def reverse_llist(llist):
before = None
current = llist.head
if current is None:
return
after = current.next
while after:
current.next = before
before = current
current = after
after = after.next
current.next = before
llist.head = current
a_llist = LinkedList()
data_list = input(‘Please enter the elements in the linked list: ‘).split()
for data in data_list:
a_llist.append(int(data))
reverse_llist(a_llist)
print(‘The reversed list: ‘)
a_llist.display()
Runtime Test Cases
Case 1:
Please enter the elements in the linked list: 7 1 30 4
The reversed list:
4 30 1 7
Case 2:
Please enter the elements in the linked list: 3
The reversed list:
3
Case 3:
Please enter the elements in the linked list: 1 2
The reversed list:
2 1