一、力扣题之排序循环链表
题目如下：航班直达！！
二、解题思路
刚看到直到题我还是很迷的，没有写过类似的题目。
当我看到官方题解时，嘿嘿嘿三个字形容此时的心情。
首先需要知道，这道题是升序的，但是当我们找到最大节点时，最大节点的next是最小节点，这是循环链表的缘故
1. 使用双指针法
双指针在链表这块题目还是特别特别好用的。
定义一个cur指针指向头节点，next指针指向头节点的下一个节点，这是初始状态。
这里需要分几种情况来讨论，拿题目的样例来看：
对插入数据的大小不同，分为几种情况：
1）当 insertVal大于cur的值，并且insertVal小于next的值时，
此时insertVal介于cur和next之间，插入它们之间即可。
2）当insertVal大于cur的值，并且cur的值大于next的值时，
此时cur是链表中的MAX节点，next是链表中的MIN节点。
而insertVal大于MAX节点，所以只需在cur和next之间插入即可。
3）当cur大于next的值，表明cur是MAX节点，next是MIN节点，并且insertVal的值小于next的值，此时insertVal小于MIN，只需在cur和next之间插入即可。
以上三种情况：都是在cur和next之间插入。
4）而如果链表为空，更容易了，题目也已经给出，如果链表为空，只需要返回插入的节点即可。
Node*insertnode = (Node*)malloc(sizeof(Node)); insertnode->val = insertVal; insertnode->next = NULL; //链表为空 if(head == NULL) { insertnode->next = insertnode; return insertnode; }
5）如果链表只有一个节点，那么也不用遍历了，在head后面插入即可，一定是有序的。
//只有一个节点 if(head->next == head) { insertnode->next = head; head->next = insertnode; return head; }
对于链表中的节点全部相同的情况，在哪里插入都可以，这种情况已经包含在上面三种情况的一种处理了，无需再单独处理。
总代码如下：
typedef struct Node Node; struct Node* insert(struct Node* head, int insertVal) { Node*insertnode = (Node*)malloc(sizeof(Node)); insertnode->val = insertVal; insertnode->next = NULL; //链表为空 if(head == NULL) { insertnode->next = insertnode; return insertnode; } //只有一个节点 if(head->next == head) { insertnode->next = head; head->next = insertnode; return head; } //两个节点及以上 struct Node*cur = head,*next = head->next; while(next!=head) { //以下三种情况都是在cur和next之间插入 if(cur->val<=insertVal && insertVal<=next->val) { break; } else if(cur->val<=insertVal && cur->val>next->val) { break; } else if(cur->val>next->val && insertVal<=next->val) { break; } cur = next; next = next->next; } insertnode->next = next; cur->next = insertnode; return head; }
2、找出最大节点，最大节点的下一个节点是最小节点，由此展开讨论
第一步1）先找出最大节点，最大节点的下一个节点是最小节点，分别记录下来。
第二步2）分情况讨论：情况与第一种方法差不多，唯一不同的是：
1、当insertVal大于最小值，并且insertVal小于最大值，此时需要从最小的节点开始遍历，直到找到第一个节点的val值大于insertVal，在该节点前面插入即可。
2、当insertVal大于cur的值，并且cur的值大于next的值时，
此时cur是链表中的MAX节点，next是链表中的MIN节点。
而insertVal大于MAX节点，所以只需在cur和next之间插入即可
3、当cur大于next的值，表明cur是MAX节点，next是MIN节点，并且insertVal的值小于next的值，此时insertVal小于MIN，只需在cur和next之间插入即可。
同样，需要在前面考虑空链表的特殊情况，而一个节点的特殊情况下面可以处理。
struct Node* insert(struct Node* head, int insertVal) { Node*insertnode = (Node*)malloc(sizeof(Node)); insertnode->val = insertVal; insertnode->next = NULL; //特殊情况 if(head == NULL) { insertnode->next = insertnode; return insertnode; } //1.找到最大节点 Node*maxnode = head, *cur = head,*next = head->next; int max = head->val; while(next!=head) { if(max<=next->val) { max = next->val; maxnode = next; } cur = next; next = next->next; } //找到最大节点了 //最大节点的next就是最小节点 Node*minnode = maxnode->next; //2.分情况讨论 //1)如果insertnode的val大于最大的或者小于最小的，则插入点在最大和最小节点之间 if(insertVal>=maxnode->val || insertVal<=minnode->val) { insertnode->next = minnode; maxnode->next = insertnode; return head; } //2)如果介于最大和最小节点之间，则从最小节点开始遍历 //直到找到第一个比insertnode大的节点 cur = minnode; next = minnode->next; while(next->val<insertVal) { cur = next; next = next->next; } //找到了 insertnode->next = next; cur->next = insertnode; return head; }
总结
第一次做到循环排序链表的题，爽歪歪，写起来很舒服，链表的题需要勤快画图分析，分析二十分钟，写代码十分钟。
