Python program to reverse the singly linked list

reverse singly linked list

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.

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

reverse singly linked list in python

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.

singly linked list reversing in python

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:

reversal of singly linked list in python

Reversed Linked List:

reverse singly linked list in python

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.

Python code to Reverse Singly Linked List

Output 1:

reverse singly linked list in python

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.

Output 2:

python program to reverse singly linked list

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.