2.8 链表计数排序
大约 2 分钟
2.8 链表计数排序
---1. 链表计数排序算法描述
- 使用
cur
指针遍历一遍链表。找出链表中最大值list_max
和最小值list_min
。 - 使用数组
counts
存储节点出现次数。 - 再次使用
cur
指针遍历一遍链表。将链表中每个值为cur.val
的节点出现次数,存入数组对应第cur.val - list_min
项中。 - 反向填充目标链表:
- 建立一个哑节点
dummy_head
,作为链表的头节点。使用cur
指针指向dummy_head
。 - 从小到大遍历一遍数组
counts
。对于每个counts[i] != 0
的元素建立一个链节点,值为i + list_min
,将其插入到cur.next
上。并向右移动cur
。同时counts[i] -= 1
。直到counts[i] == 0
后继续向后遍历数组counts
。
- 建立一个哑节点
- 将哑节点
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. 链表计数排序算法复杂度分析
- 时间复杂度:,其中 代表待排序链表中所有元素的值域。
- 空间复杂度:。