166-对链表进行插入排序-蒲公英云

166-对链表进行插入排序

电玩女神 2022-10-26 12:52 287阅读 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;
}