2.10 链表基数排序

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

1. 使用 `cur` 指针遍历链表，获取节点值位数最长的位数 `size`。
2. 从个位到高位遍历位数。因为 `0` ~ `9` 共有 `10` 位数字，所以建立 `10` 个桶。
3. 以每个节点对应位数上的数字为索引，将节点值放入到对应桶中。
4. 建立一个哑节点 `dummy_head`，作为链表的头节点。使用 `cur` 指针指向 `dummy_head`。
5. 将桶中元素依次取出，并根据元素值建立链表节点，并插入到新的链表后面。从而生成新的链表。
6. 之后依次以十位，百位，…，直到最大值元素的最高位处值为索引，放入到对应桶中，并生成新的链表，最终完成排序。
7. 将哑节点 `dummy_dead` 的下一个链节点 `dummy_head.next` 作为新链表的头节点返回。

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

class Solution:
  def radixSort(self, head: ListNode):       
      # 计算位数最长的位数
      size = 0
      cur = head
      while cur:
          val_len = len(str(cur.val))
          if val_len > size:
              size = val_len
          cur = cur.next
      
      # 从个位到高位遍历位数
      for i in range(size):
          buckets = [[] for _ in range(10)]
          cur = head
          while cur:
              # 以每个节点对应位数上的数字为索引，将节点值放入到对应桶中
              buckets[cur.val // (10 ** i) % 10].append(cur.val)
              cur = cur.next
          
          # 生成新的链表
          dummy_head = ListNode(-1)
          cur = dummy_head
          for bucket in buckets:
              for num in bucket:
                  cur.next = ListNode(num)
                  cur = cur.next
          head = dummy_head.next
          
      return head
  
  def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
      return self.radixSort(head)

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

• 时间复杂度：$O(n \times k)$。其中 $n$ 是待排序元素的个数，$k$ 是数字位数。$k$ 的大小取决于数字位的选择（十进制位、二进制位）和待排序元素所属数据类型全集的大小。
• 空间复杂度：$O(n + k)$。