NeetCode #312LC-708MediumLinked ListNC Algo100
← Back to All Problems#312 · #708 · Insert into a Sorted Circular Linked List(循环有序列表的插入)
📌 Problem Statement & Constraints
Given the head of a sorted circular linked list and an integer
insertVal, insert the value so the list remains sorted, and return the head. The list may be empty, and insertVal may be smaller than all values or larger than all values. Constraints: the number of nodes is in [0, 5 * 10^4], -10^6 <= insertVal <= 10^6.💡 Core Algorithmic Approaches
- Handle the empty list first: the new node points to itself.
- Walk the list looking for the correct insertion point. There are two cases: the value fits between
prevandcurnormally, or we are at the rotation point (whereprev.val > cur.val, i.e. the maximum wraps to the minimum) and the value is outside the range. - Also stop if we have come back to the head, which happens when every value is equal.
- Insert between
prevandcurand return the original head.
💻 Benchmark Python3 Implementation
class Solution:
def insert(self, head: "Optional[Node]", insertVal: int) -> "Node":
node = Node(insertVal)
if not head: # empty list
node.next = node
return node
prev, cur = head, head.next
while True:
if prev.val <= insertVal <= cur.val:
break # fits in the normal order
if prev.val > cur.val and (insertVal >= prev.val or insertVal <= cur.val):
break # outside the range at the rotation point
prev, cur = cur, cur.next
if prev is head:
break # all values equal -> insert anywhere
prev.next = node
node.next = cur
return head⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass around the circle in the worst case.
💾 Space Complexity
O(1): one new node.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the rotation-point case: when the value is larger than the maximum or smaller than the minimum, it must be inserted at the wrap-around, not between two ordered neighbours.
- Looping forever when all values are equal: the
prev is headcheck breaks the loop. - Returning the new node as the head: the head should remain the original head (the problem accepts any valid rotation, but returning the original is conventional).
- Not handling the empty list:
head.nextwould raise anAttributeError.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.