Insert into a Cyclic Sorted List

 Insert into a Cyclic Sorted List

내가 푼 것

넘 조잡해요 ㅠ

변수를 더 안썼다는 것에 의미를 조금 부여하고,

생성자 활용해서 next 추가한 것을 베스트 답안을 참고해서 보완해야되겠다. -> 주어진 것 잘 활용하기..

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;

    Node() {}

    Node(int _val) {
        val = _val;
        next = NULL;
    }

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
*/

class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        if (!head) {
            Node* node = new Node(insertVal);
            node->next = node;
            return node;
        } else {
            Node* temp = head;
            while (1) {
                if (head->val < head->next->val) {
                    if (head->val <= insertVal && insertVal <= head->next->val)
                        break;
                }
                else if (head->val > head->next->val) {
                    if (head->next->val <= insertVal && insertVal <= head->val)
                        if (head->val < head->next->next->val)
                            break;
                    if (head->next->val > insertVal && insertVal < head->val)
                        break;
                    if (head->val < insertVal && insertVal > head->next->val)
                        break;
                } else if (head->val == head->next->val && head->next->val == head->next->next->val) {
                    break;
                }
                head = head->next;
            }

            Node* node = new Node(insertVal);
            node->next = head->next;
            head->next = node;

            if (!node->next)
                node->next = temp;
            return temp;
        }
    }
};

 

베스트

class Solution {
public:
  Node * insert(Node * head, int insertVal) {
    if (NULL == head) {
      auto newNode = new Node(insertVal);
      newNode->next = newNode;
      return newNode;
    }
    
    auto cur = head, next = head->next;
    while (head != next) {
      if (next->val >= cur->val) {
        if (insertVal >= cur->val && insertVal <= next->val) {
          cur->next = new Node(insertVal, next);
          return head;
        }
      } else if (insertVal >= cur->val || insertVal <= next->val) {
        cur->next = new Node(insertVal, next);
        return head;
      }
      
      cur = next;
      next = cur->next;
    }
    
    cur->next = new Node(insertVal, head);
    return head;
  }
};

class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        Node* node = new Node(insertVal);
        node->next = node;
        if(!head) return node;
        
        Node *p = head, *H = NULL, *T = NULL;
        do
        {
            if(p->val > p->next->val)
            {
                H = p->next;
                T = p;
                break;
            }
            p = p->next;
        }while(p != head);
        
        if(H == NULL)
        {
            // all number in the list are same value, insert any where
            node->next = head->next;
            head->next = node;
            return head;
        }
        
        if(insertVal <= H->val || insertVal >= T->val)
        {
            // insert after T
            node->next = T->next;
            T->next = node;
            return head;
        }
        
        while(H != T)
        {
            if(H->val <= insertVal && insertVal <= H->next->val)
            {
                // insert after H
                node->next = H->next;
                H->next = node;
                break;
            }
            H = H->next;
        }
        return head;
    }
};