Question:

How to insert a new node in a sorted circular linked list using Python3

Summary

Here, we have defined a method as ‘sortedInsert’ to insert a new node with a given data value into a sorted circular linked list.

Solution

#User function Template for python3

'''

class Node:

# Constructor to initialize the node object

def __init__(self, data):

self.data = data

self.next = None

'''

class Solution:

def sortedInsert(self, head, data):

new_node = Node(data)

# Case: Empty linked list

if not head:

new_node.next = new_node

return new_node

current = head

# Case: Insert at the beginning

if data < head.data:

while current.next != head:

current = current.next

current.next = new_node

new_node.next = head

return new_node

# Case: Insert in the middle or at the end

while current.next != head and current.next.data < data:

current = current.next

new_node.next = current.next

current.next = new_node

return head

Explanation

The parameters for the sortedInsert method are a data value (data) and the head of a sorted circular linked list (head).
With the supplied data value, a new node (new_node) is created.
Empty Linked List: The new node is returned and the next node is set to itself if the linked list is empty.