2023年408算法题预测-链表之插入排序

发表于 2022-12-15 更新于 2025-03-24 分类于笔记阅读次数： Waline：本文字数： 270 阅读时长 ≈ 1 分钟

题干

获取题源请点击https://leetcode.cn/problems/insertion-sort-list/description/?languageTags=c

思路

插入排序 利用直接插入排序的算法思想，单链表无法向前遍历，需要通过三个指针完成操作。

时间复杂度：O(n²)，n为链表长度。
空间复杂度：O(1)。

C代码

感谢LeetCode用户꧁MxQuan.꧂提供的思路。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* insertionSortList(struct ListNode* head){
    if(head == NULL)                                                        //链表为空
        return NULL;
    
    struct ListNode* L = (struct ListNode*)malloc(sizeof(struct ListNode)); //辅助结点
    L->next = head;
    struct ListNode *cur = head->next, *pre = head, *tmp;

    while(cur != NULL){                                                     //遍历链表
        if(cur->val >= pre->val){                                           //寻找需要向前插入的结点
            cur = cur->next;
            pre = pre->next;
        }else{
            tmp = L;
            while(tmp->next->val < cur->val)                                //寻找插入位置
                tmp = tmp->next;
            pre->next = cur->next;                                          //进行插入
            cur->next = tmp->next;
            tmp->next = cur;
            cur = pre->next;
        }
    }

    return L->next;
}

题目答案

特别地，由于408考试所用链表大多数为带头结点的链表，且结点结构不一致，因此最后写出的代码略有不同，但思路一致。

手写版

0%