Skip to content

708. Insert into a Sorted Circular Linked List

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
 public:
  Node* insert(Node* head, int insertVal) {
    if (head == nullptr) {
      Node* newNode = new Node(insertVal);
      newNode->next = newNode;
      return newNode;
    }

    Node* prev = head;
    Node* curr = head->next;

    while (curr != head) {
      // Case 1: min <= insertVal <= max
      // Case 2: insertVal >= max or insertVal <= min
      if ((prev->val <= insertVal && insertVal <= curr->val) ||
          (prev->val > curr->val &&  // Prev is max, curr is min
           (insertVal >= prev->val || insertVal <= curr->val))) {
        // Insert the node between prev and curr
        prev->next = new Node(insertVal, curr);
        return head;
      }
      prev = prev->next;
      curr = curr->next;
    }

    // All vals in the list are identical
    prev->next = new Node(insertVal, curr);
    return head;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public Node insert(Node head, int insertVal) {
    if (head == null) {
      Node newNode = new Node(insertVal);
      newNode.next = newNode;
      return newNode;
    }

    Node prev = head;
    Node curr = head.next;

    while (curr != head) {
      // Case 1: min <= insertVal <= max
      // Case 2: insertVal >= max or insertVal <= min
      if ((prev.val <= insertVal && insertVal <= curr.val) ||
          (prev.val > curr.val && // Prev is max, curr is min
           (insertVal >= prev.val || insertVal <= curr.val))) {
        // Insert the node between prev and curr
        prev.next = new Node(insertVal, curr);
        return head;
      }
      prev = prev.next;
      curr = curr.next;
    }

    // All vals in list are identical
    prev.next = new Node(insertVal, curr);
    return head;
  }
}