166-对链表进行插入排序

电玩女神 2022-10-26 12:52 99阅读 0赞

**题目如下：**  
对一条链表进行排序算法，要求使用算法为插入排序，且时间复杂度符合O(n^2)

**解题方法：**  
1、判断链表是否为空，为空直接返回  
2、新建排序链表头和尾都指向head: shead=head;stail=head;  
3、将链表分为左右两部分，左边为一个结点：头结点head，右边为剩余结点  
4、从链表第二位开始插入排序(cur=head->next）标记右部分的第一个结点，if(cur!=NULL)  
ListNode \*s = cur->next;//给cur的next做标记  
5、cur不为空进入while循环  
**(1)判断cur->val是否小于排序链表头部值shead->val;**  
如果小于，更新排序链表头部cur->next = shead; shead = cur;  
**(2)否则判断curr->val是否大于等于排序链表尾部值stail->val;**  
如果大于等于，更新排序链表尾部stail->next = cur; stail = cur;  
**(3)否则落入排序链表中间：**  
找到排序链表位置p，使得p->val<=cur->val< p ->next->val;将cur插入到p和p->next中间  
cur->next = p->next; p->next = cur;

更新cur，cur=s；s=s->next;  
6、链表问题记得断尾求生  
stail->next = nullptr;  
7、返回排序链表  
return shead;

ListNode *insertionSortList(ListNode *head)
    {
        
        if (head==NULL)
            return head;
    
        ListNode *shead = head;
        ListNode *stail = head;
        ListNode *cur = head->next;
        if(cur!=NULL) 
        ListNode *s = cur->next;
        while (cur!=NULL)
        {
        
            if (cur->val < shead->val)
            {
        
                cur->next = shead;
                shead = cur;
            }
            else if (cur->val >= stail->val)
            {
        
                stail->next = cur;
                stail = cur;
            }
            else
            {
        
                ListNode *p = shead;
                while(p != stail)
                {
        
                    if (cur->val >= p->val && cur->val < p->next->val)
                    {
        
                        cur->next = p->next;
                        p->next = cur;
                        break;
                    }
                    p = p->next;
                }
            }
            cur = s;
            if(s!=NULL) 
            s=s->next;
        }
        stail->next = NULL;
        return shead;
    }

**代码运行如下：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/87d3e6660560404f8831855ffddbc352.png