Given a sorted circular linked list and an integer insertVal, insert a new node with the value insertVal into the list such that it remains a sorted circular linked list. The list is sorted in non-decreasing order. If the list is empty, you should create a new single-node circular list and return the reference to that node.
The input is a reference to a node in the circular linked list (not necessarily the smallest value node), and the integer insertVal to be inserted. You must insert exactly one new node, and you cannot reuse existing nodes.
Key constraints:
Before jumping into code, let's consider the nature of a circular and sorted linked list. Unlike a regular linked list, the last node points back to the first node, forming a loop. The list is sorted, but the starting node can be anywhere within the list. Our goal is to find the correct spot to insert insertVal so that the order is preserved.
A brute-force approach would be to traverse the list, collect all values, insert the new value in order, and reconstruct the list. However, this is inefficient and unnecessary. Instead, we can take advantage of the sorted and circular properties:
insertVal and the next node's value is greater than or equal to insertVal.insertVal is either smaller than all existing values or larger than all existing values, due to the circular nature.Let's break down the algorithm step by step:
head is null, create a new node with insertVal and point its next to itself, forming a single-node circular list.
head and iterate through the list using two pointers: prev (current node) and curr (next node). Since the list is circular, we need to stop when we've looped back to head.
prev, curr), check:
prev.val <= insertVal <= curr.val: insert between prev and curr.prev.val > curr.val (the "pivot" point between max and min in the circle):
insertVal >= prev.val (new max) or insertVal <= curr.val (new min), insert here.head).
This approach ensures we respect the circular and sorted properties, and always insert exactly one new node.
Let's walk through an example:
Input: Circular list: 3 -> 4 -> 1 -> (back to 3), insertVal = 2
prev = 3, curr = 4
3 <= 2 <= 4? No.prev = 4, curr = 1
4 <= 2 <= 1? No.4 > 1 (pivot point): Is 2 >= 4 or 2 <= 1? No to both.prev = 1, curr = 3
1 <= 2 <= 3? Yes! Insert between 1 and 3.
Resulting list: 3 -> 4 -> 1 -> 2 -> (back to 3)
If all values were the same (e.g., 1 -> 1 -> 1 -> (back to 1)), we could insert anywhere.
Brute-force approach:
n is the number of nodes.The optimized approach is efficient and scales well for large lists.
To insert a value into a sorted circular linked list, we leverage its sorted and circular properties to find the correct insertion point in a single traversal. By carefully handling edge cases (empty list, all same values, insert at pivot), we ensure the list remains sorted and circular, and we always insert exactly one new node. The solution is elegant due to its constant space usage and single-pass traversal, making it both efficient and robust.
# Definition for a Node.
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
class Solution:
def insert(self, head: 'Node', insertVal: int) -> 'Node':
new_node = Node(insertVal)
if not head:
new_node.next = new_node
return new_node
prev, curr = head, head.next
inserted = False
while True:
# Case 1: insertVal fits between prev and curr
if prev.val <= insertVal <= curr.val:
inserted = True
# Case 2: At the pivot point (max to min)
elif prev.val > curr.val:
if insertVal >= prev.val or insertVal <= curr.val:
inserted = True
if inserted:
prev.next = new_node
new_node.next = curr
return head
prev, curr = curr, curr.next
# If we have gone full circle
if prev == head:
break
# Case 3: All nodes have same value or no suitable place found
prev.next = new_node
new_node.next = curr
return head
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node() {}
Node(int _val, Node* _next = nullptr) {
val = _val;
next = _next;
}
};
*/
class Solution {
public:
Node* insert(Node* head, int insertVal) {
Node* newNode = new Node(insertVal);
if (!head) {
newNode->next = newNode;
return newNode;
}
Node* prev = head;
Node* curr = head->next;
bool inserted = false;
do {
// Case 1: insertVal fits between prev and curr
if (prev->val <= insertVal && insertVal <= curr->val) {
inserted = true;
}
// Case 2: At the pivot point (max to min)
else if (prev->val > curr->val) {
if (insertVal >= prev->val || insertVal <= curr->val) {
inserted = true;
}
}
if (inserted) {
prev->next = newNode;
newNode->next = curr;
return head;
}
prev = curr;
curr = curr->next;
} while (prev != head);
// Case 3: All nodes have same value or no suitable place found
prev->next = newNode;
newNode->next = curr;
return head;
}
};
/*
// Definition for a Node.
class Node {
public int val;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _next) {
val = _val;
next = _next;
}
}
*/
class Solution {
public Node insert(Node head, int insertVal) {
Node newNode = new Node(insertVal);
if (head == null) {
newNode.next = newNode;
return newNode;
}
Node prev = head;
Node curr = head.next;
boolean inserted = false;
do {
// Case 1: insertVal fits between prev and curr
if (prev.val <= insertVal && insertVal <= curr.val) {
inserted = true;
}
// Case 2: At the pivot point (max to min)
else if (prev.val > curr.val) {
if (insertVal >= prev.val || insertVal <= curr.val) {
inserted = true;
}
}
if (inserted) {
prev.next = newNode;
newNode.next = curr;
return head;
}
prev = curr;
curr = curr.next;
} while (prev != head);
// Case 3: All nodes have same value or no suitable place found
prev.next = newNode;
newNode.next = curr;
return head;
}
}
/**
* // Definition for a Node.
* function Node(val, next) {
* this.val = val;
* this.next = next;
* };
*/
/**
* @param {Node} head
* @param {number} insertVal
* @return {Node}
*/
var insert = function(head, insertVal) {
const newNode = new Node(insertVal);
if (!head) {
newNode.next = newNode;
return newNode;
}
let prev = head;
let curr = head.next;
let inserted = false;
do {
// Case 1: insertVal fits between prev and curr
if (prev.val <= insertVal && insertVal <= curr.val) {
inserted = true;
}
// Case 2: At the pivot point (max to min)
else if (prev.val > curr.val) {
if (insertVal >= prev.val || insertVal <= curr.val) {
inserted = true;
}
}
if (inserted) {
prev.next = newNode;
newNode.next = curr;
return head;
}
prev = curr;
curr = curr.next;
} while (prev !== head);
// Case 3: All nodes have same value or no suitable place found
prev.next = newNode;
newNode.next = curr;
return head;
};