148.排序链表
方法1：自顶向下的归并排序
使用归并排序算法。归并排序是一种分治算法，它将链表分成两半，然后对每一半进行排序，最后将两个有序的链表合并。由于链表不支持随机访问，我们不能像数组那样直接分割，但可以通过快慢指针找到中点，然后进行分割。
自而向下的归并排序
- 先找到链表的中间，然后将其分为左右两部分
- 分别对左右两部分进行递归，归并排序
- 将这两部分用merge函数合并起来
这个题目考察的知识点比较全面，用到的merge函数，其实就是对两个有序链表进行合并的题目21. 合并两个有序链表
# 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]:
# 方法1. 从下往上的归并排序
# 1. 先找到链表的中间mid
if not head or not head.next:
return head
slow = head
fast = head.next
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# if fast: # 偶数
# slow = slow.next
# 分割链表 !!!!!!
mid = slow.next
slow.next = None
left = self.sortList(head)
right = self.sortList(mid)
return self.mergeList(left, right)
def mergeList(self, left: Optional[ListNode], right: Optional[ListNode]) -> Optional[ListNode]:
# 方法1：递归方法，空间复杂度为O(n) 时间复杂度为O(nlogn)
if left == None:
return right
elif right == None:
return left
elif left.val < right.val:
left.next = self.mergeList(left.next, right)
return left
else:
right.next = self.mergeList(left, right.next)
return right
# 方法2：迭代方法，空间复杂度为O(1) 时间复杂度O(nlog n)
# if left == None:
# return right
# elif right == None:
# return left
# 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
# else:
# current.next = right
# return dummy.next
# 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
# 找到链表的中点
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 分割链表
mid = slow.next
slow.next = None
# 递归排序两半链表
left = self.sortList(head)
right = self.sortList(mid)
# 合并两个有序链表
return self.merge(left, right)
def merge(self, left: ListNode, right: ListNode) -> ListNode:
# 合并两个有序列表left, right
dummy = ListNode(0)
tail = dummy
while left and right:
if left.val < right.val:
tail.next = left
left = left.next
else:
tail.next = right
right = right.next
tail = tail.next
# 连接剩余部分
tail.next = left or right
return dummy.next
方法2 自底向上的归并排序
# 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: ListNode) -> ListNode:
# merge函数，将有序的head1,head2合并为一个有序的链表
def merge(head1: ListNode, head2: ListNode) -> ListNode:
dummyHead = ListNode(0)
temp, temp1, temp2 = dummyHead, head1, head2
while temp1 and temp2:
if temp1.val <= temp2.val:
temp.next = temp1
temp1 = temp1.next
else:
temp.next = temp2
temp2 = temp2.next
temp = temp.next
if temp1:
temp.next = temp1
elif temp2:
temp.next = temp2
return dummyHead.next
# sortList 函数首先计算链表的长度，然后使用一个哑节点 dummyHead 来简化头节点操作。
# subLength 表示当前需要排序的子链表的长度，初始值为1，每次循环翻倍。
# 在每次循环中，我们遍历链表，将链表分割成若干长度为 subLength 的子链表，然后使用 merge 函数将它们两两合并。
# 这段代码通过自底向上的方式实现了链表的归并排序，空间复杂度为 O(1)。
# 如果链表为空，
if not head:
return head
# 计算链表的长度
length = 0
node = head
while node:
length += 1
node = node.next
dummyHead = ListNode(0, head)
subLength = 1
while subLength < length:
prev, curr = dummyHead, dummyHead.next
while curr:
# 把链表分割成若干长度为 subLength 的子链表
# 第一个子链表的头为head1
head1 = curr
for i in range(1, subLength):
if curr.next:
curr = curr.next
else:
break
# 第二个子链表的头为head2
head2 = curr.next
curr.next = None # 将第一个子链表进行收尾
curr = head2
for i in range(1, subLength):
if curr and curr.next:
curr = curr.next
else:
break
succ = None # succ为余下的链表的开头
if curr:
succ = curr.next
curr.next = None # 将第二个子链表进行收尾
# 将合并好的结果放入到dummy后面去
merged = merge(head1, head2)
prev.next = merged
while prev.next:
prev = prev.next
curr = succ
subLength <<= 1
return dummyHead.next
原文地址：https://blog.csdn.net/weixin_43845922/article/details/142702634
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！