708. Insert into a Sorted Circular Linked List
Problem Description
This problem involves a special kind of linked list called a Circular Linked List, where the last element points back to the first, creating a closed loop. Your task is to insert a new value into the list so that the list's non-descending (sorted) order is maintained.
The nuances of this task are:
- The node you are given could be any node in the loop, not necessarily the smallest value.
- You may insert the new value into any position where it maintains the sort order.
- If the list is empty (i.e., the given node is
null
), you must create a new circular list that contains the new value and return it.
You're expected to return a reference to any node in the modified list.
Intuition
The intuition behind the solution starts with understanding the properties of a sorted circular linked list. In such a list, values gradually increase as you traverse the list, before suddenly "resetting" to the smallest value once the loop completes.
Given these properties, the solution involves handling three distinct scenarios:
-
The list is empty: If the list is empty, you create a new node that points to itself and return it as the new list.
-
Normal insertion: In a populated list, you traverse the nodes looking for the right place to insert the new value. The right place would be between two nodes where the previous node's value is less than or equal to the new value, and the next node's value is greater than or equal to the new value.
-
Edge Insertion: If you don't find such a position, it means the new value either goes before the smallest value in the list or after the largest one. This specific case occurs at the "reset" point where the last node in sort order (with the largest value) points to the first node (with the smallest value).
The algorithm involves iterating through the list, comparing the insertVal
with the current and next node values to find the correct insertion point. Once found, adjust the necessary pointers to insert the new node.
We also guarantee that we loop no more than once by comparing the current node to the initial head node. If we reach the head again, it means we've checked every node, which handles cases where all nodes in the list have the same value and the insertVal
could go anywhere.
So the high-level steps are:
- Handle the edge case where the list is empty.
- Traverse the list looking for the insertion point.
- Insert the node when the correct spot is found.
- If the loop completes without finding the exact position, insert the node just after the largest value or before the smallest value.
With this approach, we insert the new value while maintaining the list's sorted order.
Learn more about Linked List patterns.
Solution Approach
The solution implementation involves a straightforward but careful traversal of the circular linked list to maintain its sorted property after insertion.
First, we need to handle a special case:
- Empty list: If the list is empty (
head is None
), we create a new node that points to itself and return it as the new list head (circular in nature).
For a non-empty list, we follow these steps:
-
Initialize two pointers,
prev
andcurr
- starting fromhead
andhead.next
respectively. We’ll move these pointers forward until we find the correct insert location. -
Loop through the circular list and look for the correct position to insert the
insertVal
. The loop will terminate if:- We find a spot where the value directly after
prev
(curr
) is greater than or equal toinsertVal
, and the value atprev
is less than or equal toinsertVal
. This meansinsertVal
fits right betweenprev
andcurr
. - We find the point where the values "reset," indicating
prev
holds the maximum value andcurr
holds the minimum value in the list. IfinsertVal
is greater than or equal toprev.val
(greater than the list's max value) orinsertVal
is less than or equal tocurr.val
(less than the list's min value), it meansinsertVal
must be inserted here.
- We find a spot where the value directly after
-
For insertion:
- Create a new node with
insertVal
. - Adjust the
next
pointer ofprev
to point to this new node. - Set the new node's
next
pointer tocurr
.
- Create a new node with
-
Return the head of the list.
Here is the algorithm in Python code snippet from the Reference Solution Approach:
1class Node:
2 def __init__(self, val=None, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def insert(self, head: 'Optional[Node]', insertVal: int) -> 'Node':
8 node = Node(insertVal)
9 if head is None:
10 node.next = node
11 return node
12 prev, curr = head, head.next
13 while curr != head:
14 if prev.val <= insertVal <= curr.val or (
15 prev.val > curr.val and (insertVal >= prev.val or insertVal <= curr.val)
16 ):
17 break
18 prev, curr = curr, curr.next
19 prev.next = node
20 node.next = curr
21 return head
By utilizing the Node
class to instantiate the new element to be inserted and updating pointers in a singly linked list fashion, you efficiently maintain both the circular nature of the list and the sorted order with a simple yet effective algorithm that walks through the list once at most.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Suppose we have a circular sorted linked list and we need to insert a value insertVal
into the list. Our circular linked list is as follows:
13 -> 4 -> 1 2^ | 3|_________|
Here, 3
is the smallest element before the reset and 1
is the last element pointing back to 3
. Now let's say we want to insert 5
. We must find the correct spot for 2
so that the list remains sorted in non-descending order. The step will be as follows:
-
Since the list is not empty, we initialize
prev
to this node (3
) andcurr
to the next node (4
). -
We start traversing the list. As
insertVal
(5) is not between3
(prev.val
) and4
(curr.val
), we move forward. -
Now,
prev
is4
andcurr
is1
. We check:- Is
4
(prev.val
) less than5
(insertVal
) and5
(insertVal
) less than1
(curr.val
)? No. - Does
4
(prev.val
) >1
(curr.val
) indicating a reset point in the list ordering? Yes. - Is
5
(insertVal
) >=4
(prev.val
) or5
(insertVal
) <=1
(curr.val
)? The first condition is true.
- Is
-
We have reached the reset point of our list, and since
5
(insertVal
) is less than1
(curr.val
), it must be inserted between4
(prev
) and1
(curr
). -
We create a new node with the value
5
, update theprev.next
to point to this new node, and set the new node'snext
pointer tocurr
.
Now our list looks like this:
13 -> 4 -> 5 -> 1 2^ | 3|_______________|
- We return the head of the list, which can be any node in the list; in this case, we still consider the node with value
3
as the head.
Through this example, we can see how the list is effectively iterated once to find the correct spot, and how the pointers are adjusted to maintain the order after insertion. The critical part of the approach is handling the edge cases where the insertVal
is greater than the maximal value or smaller than the minimal value in the list.
Solution Implementation
1class Node:
2 def __init__(self, value=None, next_node=None):
3 self.value = value
4 self.next_node = next_node
5
6
7class Solution:
8 def insert(self, head: 'Optional[Node]', insert_value: int) -> 'Node':
9 # Create a new node with the insert_value
10 new_node = Node(insert_value)
11
12 # If the linked list is empty, initialize it with the new node
13 if head is None:
14 new_node.next_node = new_node # Point the new_node to itself
15 return new_node
16
17 # Initialize two pointers for iterating the linked list
18 previous, current = head, head.next_node
19
20 # Traverse the linked list
21 while current != head:
22 # Check if the insert_value should be inserted between previous and current
23 # The first condition checks for normal ordered insertion
24 # The second condition checks for insertion at the boundary of the largest and smallest values
25 if (
26 previous.value <= insert_value <= current.value or
27 (previous.value > current.value and (insert_value >= previous.value or insert_value <= current.value))
28 ):
29 break # Correct insertion spot is found
30
31 # Move to the next pair of nodes
32 previous, current = current, current.next_node
33
34 # Insert new_node between previous and current
35 previous.next_node = new_node
36 new_node.next_node = current
37
38 # Return the head of the modified linked list
39 return head
40
1// Class definition for a circular linked list node
2class Node {
3 public int value;
4 public Node next;
5
6 // Constructor for creating a new node without next reference
7 public Node(int value) {
8 this.value = value;
9 }
10
11 // Constructor for creating a new node with next reference
12 public Node(int value, Node next) {
13 this.value = value;
14 this.next = next;
15 }
16}
17
18class Solution {
19 // Method to insert a node into a sorted circular linked list
20 public Node insert(Node head, int insertValue) {
21 // Create the node to be inserted
22 Node newNode = new Node(insertValue);
23
24 // If the linked list is empty, point the new node to itself and return it
25 if (head == null) {
26 newNode.next = newNode;
27 return newNode;
28 }
29
30 // Pointers for tracking the current position and the previous node
31 Node previous = head, current = head.next;
32
33 // Iterate through the list to find the insertion point
34 while (current != head) {
35
36 // Check if the new node fits between previous and current nodes
37 if ((previous.value <= insertValue && insertValue <= current.value)
38 // or if it's the end/beginning of the list,
39 // as the next value is less than the previous due to the circular nature
40 || (previous.value > current.value && (insertValue >= previous.value || insertValue <= current.value))) {
41 break; // Found the place to insert
42 }
43
44 // Move to next pair of nodes
45 previous = current;
46 current = current.next;
47 }
48
49 // Insert the new node between previous and current
50 previous.next = newNode;
51 newNode.next = current;
52
53 // Return the head of the list
54 return head;
55 }
56}
57
1/*
2// Definition for a circular singly-linked list Node.
3class Node {
4public:
5 int val; // Value of the node
6 Node* next; // Pointer to the next node
7
8 Node() {}
9
10 Node(int value) {
11 val = value;
12 next = nullptr;
13 }
14
15 Node(int value, Node* nextNode) {
16 val = value;
17 next = nextNode;
18 }
19};
20*/
21
22class Solution {
23public:
24 Node* insert(Node* head, int insertVal) {
25 Node* newNode = new Node(insertVal); // Create a new node with the insertVal
26
27 // If the list is empty, initialize it with the new node which points to itself
28 if (!head) {
29 newNode->next = newNode; // Points to itself to maintain circularity
30 return newNode; // Return new node as the new head of the list
31 }
32
33 Node *prev = head;
34 Node *current = head->next;
35 bool inserted = false;
36
37 while (true) {
38 // Check if we have found the correct place to insert the new node
39 if ((prev->val <= insertVal && insertVal <= current->val) || // Case 1: Value lies between prev and current
40 (prev->val > current->val && (insertVal >= prev->val || insertVal <= current->val))) { // Case 2: At tail part after the max val or before the min val in sorted circular list
41 // Insert new node here
42 prev->next = newNode;
43 newNode->next = current;
44 inserted = true;
45 break;
46 }
47
48 prev = current;
49 current = current->next;
50
51 // If we completed one full circle around the list and didn't insert the new node, break loop to insert at the end.
52 if (prev == head) {
53 break;
54 }
55 }
56
57 // If the new node hasn't been inserted yet, it should be placed between the tail and the head.
58 // This case also covers a list with uniform values.
59 if (!inserted) {
60 prev->next = newNode;
61 newNode->next = current;
62 }
63
64 // Return the head of the list
65 return head;
66 }
67};
68
1// Definition for a circular singly-linked list node.
2class ListNode {
3 val: number;
4 next: ListNode | null;
5
6 constructor(val?: number, next?: ListNode | null) {
7 this.val = (val === undefined ? 0 : val);
8 this.next = (next === undefined ? null : next);
9 }
10}
11
12// Function to create a new node with a given value
13function createNode(value: number): ListNode {
14 return new ListNode(value);
15}
16
17// Function to insert a new node with insertVal into the circular linked list
18function insert(head: ListNode | null, insertVal: number): ListNode | null {
19 // Create a new node with the insertVal
20 const newNode = createNode(insertVal);
21
22 // If the list is empty, initialize it with the new node which points to itself
23 if (head === null) {
24 newNode.next = newNode; // Points to itself to maintain circularity
25 return newNode; // Return new node as the new head of the list
26 }
27
28 let prev = head;
29 let current = head.next;
30 let inserted = false;
31
32 do {
33 // Check if we have found the correct place to insert the new node
34 // Case 1: Value lies between prev and current
35 // Case 2: At tail part after the max val or before the min val in sorted circular list
36 if ((prev.val <= insertVal && insertVal <= current.val) ||
37 (prev.val > current.val && (insertVal >= prev.val || insertVal <= current.val))) {
38 // Insert new node here
39 prev.next = newNode;
40 newNode.next = current;
41 inserted = true;
42 break;
43 }
44
45 prev = current;
46 current = current.next;
47
48 // If we completed one full circle around the list and didn't insert the new node, break loop to insert at the end.
49 } while (prev !== head);
50
51 // If the new node hasn't been inserted yet, it should be placed between the tail and the head.
52 // This case also covers a list with uniform values.
53 if (!inserted) {
54 prev.next = newNode;
55 newNode.next = current;
56 }
57
58 // Return the head of the list
59 return head;
60}
61
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(n)
, where n
is the number of nodes in the circular linked list. This complexity arises because in the worst-case scenario, the code would iterate through all the elements of the linked list once to find the correct position to insert the new value. The while
loop continues until it returns to the head, meaning it could traverse the entire list.
Space Complexity
The space complexity of the given code is O(1)
. The only extra space used is for creating the new node to be inserted, and no additional space that grows with the size of the input linked list is used.
Learn more about how to find time and space complexity quickly using problem constraints.
You are given an array of intervals where intervals[i] = [start_i, end_i]
represent the start and end of the ith
interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.
Recommended Readings
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.