148. 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：

• 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目在范围 [0, 5 * 10^4] 内
• -10^5 <= Node.val <= 10^5

Python 解答：
1.插入排序超时

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        guard = ListNode(float('-inf'))
        cur = head
        while cur:
            nex = cur.next
            cur.next = None
            p = guard
            q = guard.next
            while q and q.val <= cur.val:
                p = p.next
                q = q.next
            p.next = cur
            cur.next = q
            cur = nex
        return guard.next

2.归并排序

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head:
            return None
        elif head.next == None:
            return head
        p, q = head, head.next
        while q and q.next:
            p = p.next
            q = q.next
            q = q.next
        head2 = p.next
        p.next = None
        l1 = self.sortList(head)
        l2 = self.sortList(head2)
        return self.merge(l1, l2)

    def merge(self, l1, l2):
        if not l1:
            return l2
        if not l2:
            return l1
        guard = ListNode(-1)
        s = guard
        while l1 and l2:
            if l1.val < l2.val:
                s.next = l1
                l1 = l1.next
                s = s.next
            else:
                s.next = l2
                l2 = l2.next
                s = s.next
        if l1:
            s.next = l1
        if l2:
            s.next = l2
        return guard.next