【Leetcode——排序的循环链表】

😊😊😊

---

一、力扣题之排序循环链表

题目如下：航班直达！！

二、解题思路

刚看到直到题我还是很迷的，没有写过类似的题目。
当我看到官方题解时，嘿嘿嘿三个字形容此时的心情。
首先需要知道，这道题是升序的，但是当我们找到最大节点时，最大节点的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;
}

总结

第一次做到循环排序链表的题，爽歪歪，写起来很舒服，链表的题需要勤快画图分析，分析二十分钟，写代码十分钟。