The sword refers to Offer II 029. Sorted circular linked list - pure linked list implementation

剑指 Offer II 029. 排序的循环链表

给定循环单调非递减列表中的一个点,写一个函数向这个列表中插入一个新元素 insertVal ,使这个列表仍然是循环升序的.

给定的可以是这个列表中任意一个顶点的指针,并不一定是这个列表中最小元素的指针.

如果有多个满足条件的插入位置,可以选择任意一个位置插入新的值,插入后整个列表仍然保持有序.

如果列表为空（给定的节点是 null）,需要创建一个循环有序列表并返回这个节点.否则.请返回原先给定的节点.

示例 1：

输入：head = [3,4,1], insertVal = 2
输出：[3,4,1,2]
解释：在上图中,有一个包含三个元素的循环有序列表,你获得值为 3 的节点的指针,我们需要向表中插入元素 2 .新插入的节点应该在 1 和 3 之间,插入之后,整个列表如上图所示,最后返回节点 3 .

示例 2：

输入：head = [], insertVal = 1
输出：[1]
解释：列表为空（给定的节点是 null）,创建一个循环有序列表并返回这个节点.

示例 3：

输入：head = [1], insertVal = 0
输出：[1,0]

It's a little more complicated,但是并没有什么,解题代码如下：

/** * Definition for a Node. * struct Node { * int val; * struct TreeNode *next; * }; */
 struct Node* f(int val,struct Node* head){
    

    struct Node *node=(struct Node*)malloc(sizeof(struct Node));
     node->val=val;
     if(head==NULL){
    
         head=node;
         head->next=head;
         return head;
     }
     
     struct Node* p=head->next;
     struct Node* pre=head;
     
     struct Node *pmin=head,*pmax=head,*premin=head;
     

     while(!(pre->val<=val&&p->val>=val)){
    
         if(p->val<=pmin->val){
    
             premin=pre;
             pmin=p;
         }
          if(p->val>=pmax->val){
    
             pmax=p;
         }
         pre=p;
         p=p->next;
         if(pre==head){
    
             break;
         }
       // printf("%d ",p->val);
     }
     if(pre->val<=val&&p->val>=val){
    
            node->next=p;
         pre->next=node;
     }
     else{
    
         if(val>=pmax->val){
    
             pre=pmax;
             p=pmax->next;
              node->next=p;
            pre->next=node;


         }
         if(val<=pmin->val){
    
             p=head,pre=head->next;
             while(true&&pre!=head){
    
                 if(p->val>pmin->val&&pre->val==pmin->val){
    
                     break;
                 }
                 p=p->next;
                 pre=pre->next;
             }

           
              node->next=pre;
              p->next=node;


         }

     }
   
  
     return head;

 }
 

struct Node* insert(struct Node* head, int insertVal) {
    
    head=f(insertVal,head);
    return head;

    
}