Python Data Structures - Circular Singly Linked List Other Related Topics

Python - Reverse the Circular Singly Linked List



While working with a circular singly linked list, sometimes it is required to reverse it. Reversing a List produces following result: if the given List is 10->20->30->40->50, after reversing the List the List becomes 50->40->30->20->10.

Reversing a List requires creating three nodes, considering that the list is not empty, which are as follows: tempNode pointing to head, prevNode pointing to head and curNode pointing to next of head. Then make next of prevNode as itself to make the first node as last node of the reversed list. After that, while the curNode is not head adjust links (unlink curNode and link it to the reversed list from front and modify curNode and prevNode to the next element in the list). At last, make the prevNode (last node) as head.

The function reverseList is created for this purpose. It is a 4-step process.

def reverseList(self):
  #1. If head is not null create three nodes
  #   prevNode - pointing to head,
  #   tempNode - pointing to head,
  #   curNode - pointing to next of head
  if(self.head != None):
    prevNode = self.head
    tempNode = self.head
    curNode = self.head.next
    
    #2. assign next of prevNode as itself to make the
    #   first node as last node of the reversed list
    prevNode.next = prevNode
    
    while(curNode != self.head):
      #3. While the curNode is not head adjust links 
      #   (unlink curNode and link it to the reversed list 
      #   from front and modify curNode and prevNode) 
      tempNode = curNode.next
      curNode.next = prevNode
      self.head.next = curNode
      prevNode = curNode
      curNode = tempNode

    #4. Make prevNode (last node) as head
    self.head = prevNode 

The below is a complete program that uses above discussed concept to reverse a given circular singly linked list.

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

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

  #Add new element at the end of the list
  def push_back(self, newElement):
    newNode = Node(newElement)
    if(self.head == None):
      self.head = newNode
      newNode.next = self.head
      return
    else:
      temp = self.head
      while(temp.next != self.head):
        temp = temp.next
      temp.next = newNode
      newNode.next = self.head

  #reverse the list
  def reverseList(self):
    if(self.head != None):
      prevNode = self.head
      tempNode = self.head
      curNode = self.head.next
      
      prevNode.next = prevNode
      
      while(curNode != self.head):
        tempNode = curNode.next
        curNode.next = prevNode
        self.head.next = curNode
        prevNode = curNode
        curNode = tempNode

      self.head = prevNode 
  
  #display the content of the list
  def PrintList(self):
    temp = self.head
    if(temp != None):
      print("The list contains:", end=" ")
      while (True):
        print(temp.data, end=" ")
        temp = temp.next
        if(temp == self.head):
          break
      print()
    else:
      print("The list is empty.")

# test the code                  
MyList = LinkedList()

#Add five elements in the list.
MyList.push_back(10)
MyList.push_back(20)
MyList.push_back(30)
MyList.push_back(40)
MyList.push_back(50)

#Display the content of the list.
MyList.PrintList()

#Reversing the list.
MyList.reverseList()
  
#Display the content of the list.
MyList.PrintList()

The above code will give the following output:

The list contains: 10 20 30 40 50 
The list contains: 50 40 30 20 10