Keshawn_lu's Blog

Leetcode 147. 对链表进行插入排序

链表
字数统计: 364阅读时长: 1 min
2020/11/20 Share

题目简介：

对链表进行插入排序。

插入排序算法：

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

示例 1：

1
2
输入: 4->2->1->3
输出: 1->2->3->4

示例 2：

1
2
输入: -1->5->3->4->0
输出: -1->0->3->4->5

思路：

每次在插入元素时，都从前往后找到正确的插入位置。

tip:

  • 当待插入的元素为目前最小的元素时，更新head为该最小元素。
  • 每个元素在插入前都需要断开与后继结点的联系。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {

        ListNode* cur = head;
        ListNode* pre = NULL;

        while(cur){

            ListNode* old = cur -> next;    //保存下一个元素
            cur -> next = NULL; //切断和下个结点的联系

            //寻找插入位置
            ListNode* temp = head;
            while(temp && temp -> val < cur -> val){

                pre = temp;
                temp = temp -> next;
            }
            
            if(pre)
                pre -> next = cur;
            else
                head = cur;  //保存更新后的开头

            if(cur != temp)
                cur -> next = temp;

            cur = old;
            pre = NULL;
        }

        return head;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网