2.8 链表计数排序

---

1. 链表计数排序算法描述

1. 使用 cur 指针遍历一遍链表。找出链表中最大值 list_max 和最小值 list_min。
2. 使用数组 counts 存储节点出现次数。
3. 再次使用 cur 指针遍历一遍链表。将链表中每个值为 cur.val 的节点出现次数，存入数组对应第 cur.val - list_min 项中。
4. 反向填充目标链表：
   1. 建立一个哑节点 dummy_head，作为链表的头节点。使用 cur 指针指向 dummy_head。
   2. 从小到大遍历一遍数组 counts。对于每个 counts[i] != 0 的元素建立一个链节点，值为 i + list_min，将其插入到 cur.next 上。并向右移动 cur。同时 counts[i] -= 1。直到 counts[i] == 0 后继续向后遍历数组 counts。
5. 将哑节点 dummy_dead 的下一个链节点 dummy_head.next 作为新链表的头节点返回。

2. 链表计数排序代码实现

class Solution:
    def countingSort(self, head: ListNode):
        if not head:
            return head
        
        # 找出链表中最大值 list_max 和最小值 list_min
        list_min, list_max = float('inf'), float('-inf')
        cur = head
        while cur:
            if cur.val < list_min:
                list_min = cur.val
            if cur.val > list_max:
                list_max = cur.val
            cur = cur.next
            
        size = list_max - list_min + 1
        counts = [0 for _ in range(size)]
        
        cur = head
        while cur:
            counts[cur.val - list_min] += 1
            cur = cur.next
            
        dummy_head = ListNode(-1)
        cur = dummy_head
        for i in range(size):
            while counts[i]:
                cur.next = ListNode(i + list_min)
                counts[i] -= 1
                cur = cur.next
        return dummy_head.next

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        return self.countingSort(head)

3. 链表计数排序算法复杂度分析

• 时间复杂度：$O(n + k)$，其中 $k$ 代表待排序链表中所有元素的值域。
• 空间复杂度：$O(k)$。

练习题目

• 0148. 排序链表

• 链表排序题目列表