1. 链表排序简介

在数组排序中，常见的排序算法有：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序等。

**而对于链表排序而言，因为链表不支持随机访问，访问链表后面的节点只能依靠 **next 指针从头部顺序遍历，所以相对于数组排序问题来说，链表排序问题会更加复杂一点。

下面先来总结一下适合链表排序与不适合链表排序的算法：

  • **适合链表的排序算法：**冒泡排序、选择排序、插入排序、归并排序、快速排序、计数排序、桶排序、基数排序。
  • **不适合链表的排序算法：**希尔排序。
  • **可以用于链表排序但不建议使用的排序算法：**堆排序。

希尔排序为什么不适合链表排序？

希尔排序：希尔排序中经常涉及到对序列中第 i + gap 的元素进行操作，其中 gap 是希尔排序中当前的步长。而链表不支持随机访问的特性，导致这种操作不适合链表，因而希尔排序算法不适合进行链表排序。

为什么不建议使用堆排序？

堆排序：堆排序所使用的最大堆 / 最小堆结构本质上是一棵完全二叉树。而完全二叉树适合采用顺序存储结构（数组）。因为数组存储的完全二叉树可以很方便的通过下标序号来确定父亲节点和孩子节点，并且可以极大限度的节省存储空间。

而链表用在存储完全二叉树的时候，因为不支持随机访问的特性，导致其寻找子节点和父亲节点会比较耗时，如果增加指向父亲节点的变量，又会浪费大量存储空间。所以堆排序算法不适合进行链表排序。

如果一定要对链表进行堆排序，则可以使用额外的数组空间表示堆结构。然后将链表中各个节点的值依次添加入堆结构中，对数组进行堆排序。排序后，再按照堆中元素顺序，依次建立链表节点，构建新的链表并返回新链表头节点。

1.0147. 对链表进行插入排序

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

插入排序 算法的步骤:

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

下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

对链表进行插入排序。

img

示例 1：

img

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

示例 2：

img

1
2
 输入: head = [-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
29
30
31
32
33
34
35
36
37
38
39
40
 # Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, val=0, next=None):
 #         self.val = val
 #         self.next = next
 
 class Solution:
     def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
         if not head or not head.next:
             return head
         
         # 创建一个哨兵节点（虚拟头节点）
         dummy = ListNode(0)
         dummy.next = head
         
         # 已排序部分的最后一个节点
         last_sorted = head
         # 当前要插入的节点
         current = head.next
         
         while current:
             if current.val >= last_sorted.val:
                 # 当前节点已经在正确位置，无需移动
                 last_sorted = last_sorted.next
             else:
                 # 从头开始找插入位置
                 prev = dummy
                 while prev.next and prev.next.val < current.val:
                     prev = prev.next
                 
                 # 插入 current 节点到 prev 和 prev.next 之间
                 last_sorted.next = current.next  # 断开 current
                 current.next = prev.next
                 prev.next = current
 
             # 移动 current 指针
             current = last_sorted.next
         
         return dummy.next