LeetCode-148. 排序链表【链表 双指针 分治 排序 归并排序】

本文主要是介绍LeetCode-148. 排序链表【链表 双指针 分治 排序 归并排序】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

给你链表的头结点 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 * 10⁴] 内
-10⁵ <= Node.val <= 10⁵

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗

解题思路一：递归的归并排序，两个关键点，找到中点mid和分割链表。前者通过快慢指针，后者通过指向None。即mid, slow.next = slow.next, None

然后对分割的链表再次进行递归分割，直到满足终止条件if not head or not head.next:
最后进行归并排序：空间复杂度：O(logn)

# 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: # termination.return headslow, fast = head, head.nextwhile fast and fast.next:fast, slow = fast.next.next, slow.nextmid, slow.next = slow.next, None # mid  奇数个节点找到中点右边，偶数个节点找到中心右边的节点。slow.next =  None 分割链表left, right = self.sortList(head), self.sortList(mid) # 递归分割h = res = ListNode(0)while left and right: # 归并排序if left.val < right.val:h.next, left = left, left.nextelse:h.next, right = right, right.nexth = h.nexth.next = left if left else rightreturn res.next

时间复杂度：O(nlogn)
空间复杂度：O(logn)

解题思路二：归并排序（从底至顶直接合并）非递归

# 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:h, length, intv = head, 0, 1while h: h, length = h.next, length + 1res = ListNode(0)res.next = head# merge the list in different intv.while intv < length:pre, h = res, res.nextwhile h:# get the two merge head `h1`, `h2`h1, i = h, intvwhile i and h: h, i = h.next, i - 1if i: break # no need to merge because the `h2` is None.h2, i = h, intvwhile i and h: h, i = h.next, i - 1c1, c2 = intv, intv - i # the `c2`: length of `h2` can be small than the `intv`.# merge the `h1` and `h2`.while c1 and c2:if h1.val < h2.val: pre.next, h1, c1 = h1, h1.next, c1 - 1else: pre.next, h2, c2 = h2, h2.next, c2 - 1pre = pre.nextpre.next = h1 if c1 else h2while c1 > 0 or c2 > 0: pre, c1, c2 = pre.next, c1 - 1, c2 - 1pre.next = h intv *= 2return res.next

详见https://leetcode.cn/problems/sort-list/solutions/13728/sort-list-gui-bing-pai-xu-lian-biao-by-jyd
时间复杂度：O(nlogn)
空间复杂度：O(1)

解题思路三：0

时间复杂度：O(n)
空间复杂度：O(n)

这篇关于LeetCode-148. 排序链表【链表 双指针 分治 排序 归并排序】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---