### ListNode 介绍 在 Python 里，`ListNode` 通常用来表示链表中的节点。链表属于线性数据结构，由一系列节点构成，每个节点包含一个值和一个指向下一个节点的指针。以下是 `ListNode` 类的定义示例： ```python class ListNode: def __init__(self, x): self.val = x self.next = None ``` 在这个类定义中，`__init__` 方法是构造函数，`self.val` 用于存储节点的值，`self.next` 是指向下一个节点的指针，初始值设为 `None`，意味着链表末尾节点的 `next` 指针为空。 ### ListNode 在排序操作中的应用 由于链表不支持随机访问，访问链表后面的节点只能依靠 `next` 指针从头部顺序遍历，所以相对于数组排序问题来说，链表排序问题会更加复杂一点 [^2]。常见的可用于链表排序的算法有归并排序和插入排序。 #### 归并排序 归并排序的核心思想是分治法，先将链表不断拆分，再将拆分后的子链表合并成有序链表。 ```python class ListNode: def __init__(self, x): self.val = x self.next = None def merge(l1, l2): dummy = ListNode(0) tail = dummy while l1 and l2: if l1.val < l2.val: tail.next = l1 l1 = l1.next else: tail.next = l2 l2 = l2.next tail = tail.next tail.next = l1 if l1 else l2 return dummy.next def get_middle(head): if not head: return head slow = head fast = head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next return slow def sortList(head): if not head or not head.next: return head middle = get_middle(head) next_to_middle = middle.next middle.next = None left = sortList(head) right = sortList(next_to_middle) return merge(left, right) ``` #### 插入排序 插入排序的思路是将未排序的数据逐个插入到已排序序列的合适位置。 ```python class ListNode: def __init__(self, x): self.val = x self.next = None def insertionSortList(head): dummy = ListNode(0) dummy.next = head curr = head while curr and curr.next: if curr.val <= curr.next.val: curr = curr.next else: prev = dummy while prev.next.val < curr.next.val: prev = prev.next temp = curr.next curr.next = temp.next temp.next = prev.next prev.next = temp return dummy.next ```