对链表进行插入排序

[编程题]对链表进行插入排序

热度指数：1950 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

对链表进行插入排序，

从链表第一个元素开始可以视为部分已排序，每次操作从链表中移除一个元素，然后原地将移除的元素插入到已排好序的部分。

数据范围：链表长度满足 $1 \le n \le 1000\$ ，链表中每个元素满足 $|val| \le 10000 \$

例如输入{2,4,1}时，对应的返回值为{1,2,4}，转换过程如下图所示：

示例1

输入

{1,2,3}

输出

{1,2,3}

示例2

输入

{2,4,1}

输出

{1,2,4}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

吾辈长歌

最通俗易懂的代码

struct ListNode* insertionSortList(struct ListNode* head ) 
{
    if(head==NULL)
        return NULL;

    struct ListNode *dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode *p = dummy->next->next;
    struct ListNode *q = dummy;
    struct ListNode *cur = dummy->next;

    while(p!=NULL)
    {
        while(q->next!=p)
        {
            if(q->next->val>p->val)
            {
                cur->next = p->next;
                p->next = q->next;
                q->next = p;
                break;
            }

            q = q->next;
        }

        cur = p;
        p = p->next;
        q = dummy;
    }

    return dummy->next;
}

发表于 2023-04-13 20:31:36 回复(0)