# 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; } }