LeetCode: 148. Sort List

题目

原题地址：https://leetcode.com/problems/sort-list/

Given the head of a linked list, return the list after sorting it in ascending order.

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Example 1:

image1

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

image2

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

Input: head = []
Output: []

Constraints:

  • The number of nodes in the list is in the range [0, 5 * 10^4].
  • -10^5 <= Node.val <= 10^5

解法

使用归并排序的方法对链表进行排序

基本思路如下：

  • 递归切分链表为两部分，分别对两部分进行排序，然后再合并排序过后的各个部分。
  • 二分链表需要找到链表中间元素，可以通过快慢指针的方法寻找：慢指针每次移动一步，快指针每次移动两步，当快指针到达链表尾部时，慢指针刚好在链表中间位置。
  • 合并排序后的部分可以参考前面的 LeetCode: 21. Merge Two Sorted Lists

这个方法的 Python 代码类似下面这样:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def sortList(self, head):
        if head is None or head.next is None:
            return head

        mid = self.find_mid(head)
        left = self.sortList(head)
        right = self.sortList(mid)

        return self.merge_two_link(left, right)

    def find_mid(self, head):
        pre = None
        slow, fast = head, head
        while fast is not None and fast.next is not None:
            pre = slow
            slow = slow.next
            fast = fast.next.next

        # 通过 pre.next=None 将链表从中间切断为两个链表
        if pre is not None:
            pre.next = None
        return slow

    def merge_two_link(self, l1, l2):
        dummy = ListNode()
        tail = dummy
        while l1 is not None and l2 is not None:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next

        if l1 is not None:
            tail.next = l1
        if l2 is not None:
            tail.next = l2

        return dummy.next

Comments