C语言每日一题（60）对链表进行插入排序

对编程一片赤诚的小吴

发布于 2024-02-22 10:36:35

680

发布于 2024-02-22 10:36:35

文章被收录于专栏：热爱编程的证据热爱编程的证据

题目链接

力扣网 147 对链表进行插入排序

题目描述

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

对链表进行插入排序。

示例 1：

输入: head = [4,2,1,3]
输出: [1,2,3,4]

示例 2：

输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]

提示：

列表中的节点数在 [1, 5000]范围内
-5000 <= Node.val <= 5000

思路分析

知识点：链表、插入排序

解析：

设置一个哨兵位，方便我们进行插入，接下来说明一下需要定义的指针变量

1.lastsorted：指向待插入链表的最后一个位置的指针（插入排序将插入位置前面的部分看成是已经有序的），最开始指向head。

2.cur：指向需要进行判断是否需要插入的结点，最开始指向head.next。

3.prev：指向插入位置的前一个结点，插入时使用，最开始指向dummy（哨兵位）

插入过程：

1.首先判断cur指向的结点值是否小于lastsorted，如果大于的话，lastsorted往下走。

小于的话，prev指针从dummy开始遍历，找到需要插入的结点的前一个结点进行插入操作

链表的插入操作：将lastsorted指针的next指向cur的next，cur的next指向prev的next，也就是lastsorted，随后prev的next指向cur即可。

走完上面一趟后，不管cur的值是否大于还是小于lastsorted的值，cur都往下走。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* insertionSortList(struct ListNode* head) {
    if(head==NULL)
    {
        return head;
    }
    struct ListNode* dummy=(struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->val=-1;
    dummy->next=head;
    struct ListNode* lastshorted=head;
    struct ListNode* cur=head->next;
    while(cur)
    {
        if(lastshorted->val<=cur->val)
        {
            lastshorted=lastshorted->next;
        }
        else
        {
            struct ListNode* prev=dummy;
            while(prev->next->val<=cur->val)
            {
                prev=prev->next;
            }
            lastshorted->next=cur->next;
            cur->next=prev->next;
            prev->next=cur;
        }
        cur=lastshorted->next;
    }
    return dummy->next;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-02-21，如有侵权请联系 cloudcommunity@tencent.com 删除

指针