⚡Flashcard Drill➔
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

  1. Handle the empty list first: the new node points to itself.
  2. Walk the list looking for the correct insertion point. There are two cases: the value fits between prev and cur normally, or we are at the rotation point (where prev.val > cur.val, i.e. the maximum wraps to the minimum) and the value is outside the range.
  3. Also stop if we have come back to the head, which happens when every value is equal.
  4. Insert between prev and cur and 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 head check 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.next would raise an AttributeError.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems