LeetCode147-对链表进行插入排序

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/insertion-sort-list/

中文链接：https://leetcode-cn.com/problems/insertion-sort-list/

题目详述

对链表进行插入排序。

img
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

  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

题目详解

  • 为了方便操作，新建了一个哑结点作为头结点。
  • 需要注意在单链表中寻找结点插入位置的过程。
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
public class LeetCode_00147 {

    /**
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * @param head 待排序链表头结点
     * @return 排序后链表的头结点
     */
    public ListNode insertionSortList(ListNode head) {
        // 新建一个哑结点 dummy，代表链表已排序部分的头部
        ListNode dummy = new ListNode(-1);
        // cur 指向待排序链表的头部
        ListNode cur = head;
        while (cur != null) {
            // 由于是单链表，从前往后遍历已排序部分，找到待排序结点的正确插入位置
            ListNode p = dummy;
            while (p.next != null && p.next.val <= cur.val) {
                p = p.next;
            }
            // 将 cur 插入到 p 之后
            ListNode next = cur.next;
            cur.next = p.next;
            p.next = cur;
            cur = next;
        }
        return dummy.next;
    }
}