[LeetCode]148. 排序链表（Sort List）

题目描述

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

解题思路

使用归并排序的思想，用快慢指针将原始的链表分为两部分，这两部分又递归调用函数，最终将各自有序的子链表合并起来。

代码

Python 3.6

# 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, fast = head, head
        while fast.next is not None and fast.next.next is not None:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None
        left_head = self.sortList(head)
        right_head = self.sortList(mid)
        return self.merge(left_head, right_head)
    
    def merge(self, head1, head2):
        if head1 is None:
            return head2
        if head2 is None:
            return head1
        if head1.val <= head2.val:
            head1.next = self.merge(head1.next, head2)
            return head1
        else:
            head2.next = self.merge(head1, head2.next)
            return head2

执行用时: 448 ms
内存消耗: 43 MB