LeetCode 148. Sort List.jpg

LeetCode 148. Sort List

Description

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4
Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

描述

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

示例 1:

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

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

思路

• 为了达到O(nlogn)的空间复杂度和O(1)的时间复杂度，此题目使用归并排序达到时间复杂度，使用链表来达到空间复杂度.
• 归并排序使用的递归的解法会使得空间复杂度达到O(n),我们使用循环来实现.
• 有n个节点，归并排序的方法是：第一遍单个元素与单个元素归并，第二遍两两归并，第三遍四四归并，最后一遍前n/2与后n/2归并，总共将执行⌈log2(N)⌉次.
• 我们使用循环来实现这个过程，涉及到的主要操作有拆分链表，归并链表.
• 拆分链表，给定其实拆分位置和需要拆分的个数，将边表切断。
• 归并链表，根据链表值的大小，对链表从小到大进行归并.

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-01-13 15:09:56
# @Last Modified by:   何睿
# @Last Modified time: 2019-01-13 21:26:38

import math


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 如果为空或者只有一个元素则直接返回
        if not head or not head.next:
            return head
        # count表示节点个数
        count, node = 0, head
        # 获取节点的个数
        while node:
            count += 1
            node = node.next
        # res作为辅助节点
        res = ListNode(0)
        # 将res节点next指针指向头节点
        res.next = head
        tail, _next = None, None
        # 归并排序一共将执行log2(n)向上取整次
        for i in range(math.ceil((math.log(count, 2)))):
            # nums表示每次将排序的元素个数
            nums = 2**i
            # tail为辅助节点，表示已经排好序的末尾节点
            tail = res
            # _next初始化为head节点，表示下一次排序的起始节点
            _next = res.next
            while _next:
                # left 表示归并排序的第一个序列
                left = _next
                # right表示归并排序的第二个序列
                # nums为当前排序每个节点的个数
                right = self._depart(left, nums - 1)
                # _next表示下一次将要排序的起始位置
                _next = self._depart(right, nums - 1)
                # 对两个链表进行归并排序，并返回其首节点，尾节点
                sortedhead, sortedtail = self._merge(left, right)
                # 将上次排好序的尾节点与新排好序的尾节点相连
                tail.next = sortedhead
                # tail更新为新排好序的尾节点
                tail = sortedtail
        temp = res
        res = res.next
        # 删除刚才新建的辅助节点
        del temp
        return res

    def _depart(self, head, steps):
        # steps表示移动的步数
        # 对链表进行拆分操作
        node = head
        # 向后移动steps步
        while node and steps:
            node = node.next
            steps -= 1
        res = node.next if node else None
        # 切断链表
        if node: node.next = None
        # res表示下一个子链表排序的起始位置
        return res

    def _merge(self, left, right):
        # 声明一个辅助节点
        node = ListNode(0)
        tail = node
        # 当left和right都不为空才执行
        while left and right:
            # 我们让left始终指向较小值的节点
            if left.val > right.val: left, right = right, left
            # 更新tail节点的指向
            tail.next = left
            left = left.next
            tail = tail.next
        # 如果left 节点还有剩余，则将剩余节点添加到已经排序的节点末尾
        if left: tail.next = left
        # 如果right节点还有剩余，则将剩余节点添加到已经排序的节点末尾
        if right: tail.next = right
        res, tail = node.next, node
        while tail.next:
            tail = tail.next
        # 删除刚刚新建的辅助节点
        del node
        return res, tail

源代码文件在这里.
©本文首发于何睿的博客，欢迎转载，转载需保留文章来源，作者信息和本声明.