Python program to reverse the 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

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.

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

class LinkedList:
	 def __init__(self):
		self.head = None
		self.head = None

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.

def pushLast(self, newElement):
    # Create a new node with the given data
    newNode = Node(newElement)

    # If the linked list is empty, set the new node as head
    if self.head is None:
        self.head = newNode
        return
    else:
        # Traverse to the last node
        temp = self.head
        while temp.next is not None:
            temp = temp.next

        # Link the last node to the new node
        temp.next = newNode

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:

Python code to Reverse Singly Linked List

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


class SinglyLinkedList:

    def __init__(self):
        self.head = None

    def push(self, new_data):
        """Add element at the beginning"""
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    def pushLast(self, new_data):
        """Add element at the end"""
        new_node = Node(new_data)
        if self.head is None:
            self.head = new_node
            return
        temp = self.head
        while temp.next:
            temp = temp.next
        temp.next = new_node

    def reverse(self):
        """Reverse the linked list"""
        prev = None
        current = self.head
        while current:
            next = current.next
            current.next = prev
            prev = current
            current = next
        self.head = prev

    def __str__(self):
        """Return string representation of the list"""
        result = []
        temp = self.head
        while temp:
            result.append(str(temp.data))
            temp = temp.next
        return " -> ".join(result) if result else "[Empty List]"


# Main program
s = SinglyLinkedList()

print("Linked List Menu:")
print("1: Add element at the beginning")
print("2: Add element at the end")
print("3: Reverse the linked list")
print("4: Display the linked list")
print("0: Exit")

while True:
    try:
        choice = int(input("\nEnter your choice: "))
    except ValueError:
        print("[INVALID INPUT]: Please enter a valid number.")
        continue

    if choice == 0:
        print("Exiting program.")
        break
    elif choice == 1:
        data = input("Enter element to add at beginning: ")
        s.push(data)
    elif choice == 2:
        data = input("Enter element to add at end: ")
        s.pushLast(data)
    elif choice == 3:
        s.reverse()
        print("Linked list reversed successfully.")
    elif choice == 4:
        print("Linked list contents:")
        print(s)
    else:
        print("[INVALID INPUT]: Please enter a valid menu option.")

Output:

Linked List Menu:
1: Add element at the beginning
2: Add element at the end
3: Reverse the linked list
4: Display the linked list
0: Exit

Enter your choice: 1
Enter element to add at beginning: 5

Enter your choice: 1
Enter element to add at beginning: 7

Enter your choice: 1
Enter element to add at beginning: 9

Enter your choice: 1
Enter element to add at beginning: 2

Enter your choice: 3
Linked list reversed successfully.

Enter your choice: 4
Linked list contents:
5 -> 7 -> 9 -> 2

Enter your choice: 0
Exiting program.