LeetCode 148. 排序链表
2021-04-19 18:26
标签：node not list val init 复杂 排序 slow linked 在?O(n?log?n) 时间复杂度和常数级空间复杂度下，对链表进行排序。 示例 1: 示例 2: LeetCode 148. 排序链表 标签：node not list val init 复杂 排序 slow linked 原文地址：https://www.cnblogs.com/sandy-t/p/13288142.html
输入: 4->2->1->3
输出: 1->2->3->4
输入: -1->5->3->4->0
输出: -1->0->3->4->5# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
slow = head
fast = head.next
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
pre_head = ListNode(None)
cur = pre_head
p1 = self.sortList(head)
p2 = self.sortList(mid)
while p1 is not None and p2 is not None:
#print(p1.val,p2.val)
if p1.val
文章标题：LeetCode 148. 排序链表
文章链接：http://soscw.com/index.php/essay/76766.html