【LeetCode刷题】排序链表

给你链表的头结点head，请将其按升序排列并返回排序后的链表。

示例 1：

输入：head = [4,2,1,3]输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]输出：[-1,0,3,4,5]

示例 3：

输入：head = []输出：[]

提示：

• 链表中节点的数目在范围[0, 5 *]内
• <= Node.val <=

解题思路（自顶向下归并排序）

1. 分治拆分：用快慢指针找到链表中点，将原链表拆分为左右两个子链表；
2. 递归排序：对左右子链表分别递归执行排序；
3. 合并有序链表：将排序后的左右子链表合并为一个有序链表，最终得到完整的排序结果。

Python代码

from typing import Optional # Definition for singly-linked list. class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]: # 递归终止条件：链表为空或只有一个节点（已有序） if not head or not head.next: return head # 步骤1：找到链表中点，拆分链表为左右两部分 mid = self.find_mid(head) right_head = mid.next mid.next = None # 断开链表，拆分出左、右子链表 # 步骤2：递归排序左右子链表 left_sorted = self.sortList(head) right_sorted = self.sortList(right_head) # 步骤3：合并两个有序子链表 return self.merge_two_sorted_lists(left_sorted, right_sorted) def find_mid(self, head: ListNode) -> ListNode: """用快慢指针找链表中点（慢指针最终指向左半部分的尾节点）""" slow = head fast = head.next # 让快指针多走一步，确保拆分后左半部分不超过右半部分 while fast and fast.next: slow = slow.next fast = fast.next.next return slow def merge_two_sorted_lists(self, l1: ListNode, l2: ListNode) -> ListNode: """合并两个有序链表，返回合并后的头节点""" dummy = ListNode(0) # 哑节点，简化合并逻辑 current = dummy while l1 and l2: if l1.val <= l2.val: current.next = l1 l1 = l1.next else: current.next = l2 l2 = l2.next current = current.next # 连接剩余节点（其中一个链表已遍历完） current.next = l1 if l1 else l2 return dummy.next # ====================== 辅助函数（测试用） ====================== def create_linked_list(nums: list) -> Optional[ListNode]: """根据列表创建链表，返回头节点""" if not nums: return None dummy = ListNode(0) current = dummy for num in nums: current.next = ListNode(num) current = current.next return dummy.next def print_linked_list(head: Optional[ListNode]) -> None: """打印链表（格式：val1 -> val2 -> ... -> None）""" current = head result = [] while current: result.append(str(current.val)) current = current.next print(" -> ".join(result) + " -> None") # ====================== 测试用例 ====================== if __name__ == "__main__": solution = Solution() # 测试用例1：基础用例（4→2→1→3） print("===== 测试用例1 =====") head1 = create_linked_list([4, 2, 1, 3]) print("排序前链表：", end="") print_linked_list(head1) sorted_head1 = solution.sortList(head1) print("排序后链表：", end="") print_linked_list(sorted_head1) # 测试用例2：含负数、零的用例（-1→5→3→4→0） print("\n===== 测试用例2 =====") head2 = create_linked_list([-1, 5, 3, 4, 0]) print("排序前链表：", end="") print_linked_list(head2) sorted_head2 = solution.sortList(head2) print("排序后链表：", end="") print_linked_list(sorted_head2) # 测试用例3：空链表 print("\n===== 测试用例3 =====") head3 = create_linked_list([]) print("排序前链表：", end="") print_linked_list(head3) sorted_head3 = solution.sortList(head3) print("排序后链表：", end="") print_linked_list(sorted_head3) # 测试用例4：单节点链表 print("\n===== 测试用例4 =====") head4 = create_linked_list([7]) print("排序前链表：", end="") print_linked_list(head4) sorted_head4 = solution.sortList(head4) print("排序后链表：", end="") print_linked_list(sorted_head4)

LeetCode提交代码

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]: # 递归终止条件：链表为空或只有一个节点（已有序） if not head or not head.next: return head # 步骤1：找到链表中点，拆分链表为左右两部分 mid = self.find_mid(head) right_head = mid.next mid.next = None # 断开链表，拆分出左、右子链表 # 步骤2：递归排序左右子链表 left_sorted = self.sortList(head) right_sorted = self.sortList(right_head) # 步骤3：合并两个有序子链表 return self.merge_two_sorted_lists(left_sorted, right_sorted) def find_mid(self, head: ListNode) -> ListNode: """用快慢指针找链表中点（慢指针最终指向左半部分的尾节点）""" slow = head fast = head.next # 让快指针多走一步，确保拆分后左半部分不超过右半部分 while fast and fast.next: slow = slow.next fast = fast.next.next return slow def merge_two_sorted_lists(self, l1: ListNode, l2: ListNode) -> ListNode: """合并两个有序链表，返回合并后的头节点""" dummy = ListNode(0) # 哑节点，简化合并逻辑 current = dummy while l1 and l2: if l1.val <= l2.val: current.next = l1 l1 = l1.next else: current.next = l2 l2 = l2.next current = current.next # 连接剩余节点（其中一个链表已遍历完） current.next = l1 if l1 else l2 return dummy.next

程序运行结果展示

===== 测试用例1 ===== 排序前链表：4 -> 2 -> 1 -> 3 -> None 排序后链表：1 -> 2 -> 3 -> 4 -> None ===== 测试用例2 ===== 排序前链表：-1 -> 5 -> 3 -> 4 -> 0 -> None 排序后链表：-1 -> 0 -> 3 -> 4 -> 5 -> None ===== 测试用例3 ===== 排序前链表： -> None 排序后链表： -> None ===== 测试用例4 ===== 排序前链表：7 -> None 排序后链表：7 -> None

总结

本文实现了一个链表排序算法，采用自顶向下的归并排序方法。算法分为三个步骤：

（1）使用快慢指针找到链表中点并拆分链表；

（2）递归排序左右子链表；

（3）合并两个有序子链表。

该方法时间复杂度为O(nlogn)，空间复杂度为O(logn)。文中提供了完整的Python实现，包括链表创建、打印等辅助函数，并通过多个测试用例验证了算法的正确性，包括基础用例、含负数和零的用例、空链表和单节点链表等特殊情况。