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
32
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: the minimum <= insertVal <= the maximum
      // Case 2: insertVal >= the maximum or insertVal <= the minimum
      if ((prev->val <= insertVal && insertVal <= curr->val) ||
          // `prev` is the maximum and `curr` is the minimum
          (prev->val > curr->val &&
           (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 the values 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: the minimum <= insertVal <= the maximum
      // Case 2: insertVal >= the maximum or insertVal <= the minimum
      if ((prev.val <= insertVal && insertVal <= curr.val) ||
          // `prev` is the maximum and `curr` is the minimum
          (prev.val > curr.val && (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 the values in the list are identical.
    prev.next = new Node(insertVal, curr);
    return head;
  }
}