In this tutorial, we are going to learn the python program to reverse the singly linked list.
Problem Statement
Our program will take the linked list elements from the user as the input and return the reversed linked list.
For example:
Case1: If the user input the linked list as 1, 2, 3, 4.
The output should be “4, 3, 2, 1”.
Case2: If the user input the linked list as 7, 9, 1, 0.
The output should be 0, 1, 9, 7.
[elementor-template id=”5257″]
What is a single linked list?
A linked list is the collection of elements that are connected via the memory address of successor elements. A linked list can also be defined as an unordered collection of data that is connected with a link to the next data. The data element has another block that contains the address of the next element of the singly linked list.
Creation of singly linked list
The singly linked list is a linear records shape wherein every element of the listing incorporates a pointer which factors to the following detail inside the listing. A node is referring the elements of the linked list. Each node has two components: data and next pointer, which factors the following node within the listing. The first node of the list is called the head, and the closing node of the list is called a tail. The last node of the list contains a pointer to the null. With the help of traversal, each node can be linearly accessed from the head of the list.
The linked list is created using the node class. We create a node object and another class LinkedList to use this node object.
Inserting node at the end of singly linked list
In this case, the new element is added at the end of the linked list.
Inserting a new element at the end of the linked list involves some logic:-
i. Create a new node of the linked list.
ii. Traverse to the last element of the list.
iii. Link the next pointer of the last node to the newly created list and the next pointer of the newly created list to Null.
Now let’s have a look at the program to insert an element or node at the end of the linked list.
Reversing the singly linked list
Our program will reverse the nodes by changing the direction of the pointer and interchanging the “Head” and “Null” values. Original linked list:
Reversed Linked List:
Now let’s design the algorithm.
Algorithm to Reverse the singly linked list
Step 1: Start
Step 2: Create a linked list
Step 3: Create pushLast() function to push the elements of the liked list entered by the user.
i. Create a new node of the linked list.
ii. Traverse to the last element of the list.
iii. Link the next pointer of the last node to the newly created list and the next pointer of the newly create list to Null.
Step 4: Display the original linked list using the show() function.
Step 5: Create a reverse() function to reverse the linked list.
reverse(self):
prev = None
current = self.head
while(current is not None):
next = current.next
current.next = prev
prev = current
current = next
self.head = prev
Step 6: return the contents of the reversed linked list using the show() function.
Step 7: Stop
Now let’s code the above algorithm in python code.
[elementor-template id=”5253″]
Python code to Reverse Singly Linked List
Output 1:
Explanation
The linked list creation in this example is shown with steps, where all the elements getting added at the beginning of the linked list:
i. Head–>5
ii. Head–>5–>4
iii. Head–>5–>4–>3
iv. Head–>5–>4–>3–>2
v. Head–>5–>4–>3–>2–>1
the generated linked list is 5–>4–>3–>2–>1.
The reverse of generated linked list is 1–>2–>3–>4–>5.
[elementor-template id=”5256″]
Output 2:
Explanation
The linked list creation in this example is shown with steps where all the elements getting added at the beginning of the linked list:
i. Head–>80
ii. Head–>80–>51
iii. Head–>80–>51–>1
iv. Head–>80–>51–>1–>54
v. Head–>80–>51–>1–>54–>187
the generated linked list is 80–>51–>1–>54–>187.
The reverse of generated linked list is 187–>51–>1–>54–>80.