LeetCode|148.排序链表

LeetCode习题答案汇总

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

示例 1:

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

输入: -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 not head or not head.next:
            return head
        res = []
        while head:
            res.append(head.val)
            head = head.next
        res.sort(reverse=True)
        h = pos = ListNode(None)
        while res:
            pos.next = ListNode(res.pop())
            pos = pos.next
        return h.next

结果：