2.4 链表选择排序

---

1. 链表选择排序算法描述

1. 使用两个指针 node_i、node_j。node_i 既可以用于控制外循环次数，又可以作为当前未排序链表的第一个链节点位置。
2. 使用 min_node 记录当前未排序链表中值最小的链节点。
3. 每一趟排序开始时，先令 min_node = node_i（即暂时假设链表中 node_i 节点为值最小的节点，经过比较后再确定最小值节点位置）。
4. 然后依次比较未排序链表中 node_j.val 与 min_node.val 的值大小。如果 node_j.val < min_node.val，则更新 min_node 为 node_j。
5. 这一趟排序结束时，未排序链表中最小值节点为 min_node，如果 node_i != min_node，则将 node_i 与 min_node 值进行交换。如果 node_i == min_node，则不用交换。
6. 排序结束后，继续向右移动 node_i，重复上述步骤，在剩余未排序链表中寻找最小的链节点，并与 node_i 进行比较和交换，直到 node_i == None 或者 node_i.next == None 时，停止排序。
7. 返回链表的头节点 head。

2. 链表选择排序实现代码

class Solution:
    def sectionSort(self, head: ListNode):
        node_i = head
        # node_i 为当前未排序链表的第一个链节点
        while node_i and node_i.next:
            # min_node 为未排序链表中的值最小节点
            min_node = node_i
            node_j = node_i.next
            while node_j:
                if node_j.val < min_node.val:
                    min_node = node_j
                node_j = node_j.next
            # 交换值最小节点与未排序链表中第一个节点的值
            if node_i != min_node:
                node_i.val, min_node.val = min_node.val, node_i.val
            node_i = node_i.next
        
        return head

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

3. 链表选择排序算法复杂度分析

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(1)$。

练习题目

• 0148. 排序链表(链表选择排序会超时，仅做练习)

• 链表排序题目列表