LeetCode 148. Sort List 题解

LeetCode 148. Sort List 题解题目描述给你链表的头结点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 [] 输出[]解题思路方法归并排序思路找到链表的中点将链表分成两个子链表递归地对两个子链表进行排序将排序后的两个子链表合并成一个有序链表复杂度分析时间复杂度O(n log n)其中 n 是链表的长度。归并排序的时间复杂度是 O(n log n)。空间复杂度O(log n)其中 n 是链表的长度。递归调用的栈空间取决于递归的深度最多为 O(log n)。代码实现方法归并排序# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # 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 # 找到链表的中点 mid self.find_mid(head) # 分割链表 right mid.next mid.next None left head # 递归地对两个子链表进行排序 left self.sortList(left) right self.sortList(right) # 合并两个排序后的子链表 return self.merge(left, right) def find_mid(self, head): # 使用快慢指针找到链表的中点 slow head fast head.next while fast and fast.next: slow slow.next fast fast.next.next return slow def merge(self, left, right): # 合并两个有序链表 dummy ListNode(0) current dummy while left and right: if left.val right.val: current.next left left left.next else: current.next right right right.next current current.next # 处理剩余的节点 if left: current.next left if right: current.next right return dummy.next测试用例测试用例 1输入head [4,2,1,3]输出[1,2,3,4]测试用例 2输入head [-1,5,3,4,0]输出[-1,0,3,4,5]测试用例 3输入head []输出[]总结本题是链表的经典问题主要考察对链表操作和归并排序算法的理解和应用。通过使用归并排序我们可以在 O(n log n) 的时间复杂度内对链表进行排序。归并排序的核心思想是将链表分成两个子链表递归地对两个子链表进行排序然后将排序后的两个子链表合并成一个有序链表。这种方法不仅适用于排序链表问题还可以应用于许多其他需要排序的场景。掌握归并排序的思想对于解决这类问题非常重要。