python实现leetcode之148. 排序链表

解题思路

计算长度
找到中点
一分为二，分开排序
然后归并

148. 排序链表

代码

# 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:
        return merge_sort(head, len_of(head))


def len_of(head):
    if not head: return 0
    return len_of(head.next) + 1


def jump(head, step):
    if not step: return head
    return jump(head.next, step-1)


def merge_sort(li, count):
    half = count//2
    if not half: return li  # 长度小于等于1
    second = jump(li, half-1)
    tmp = second.next
    second.next = None
    left = merge_sort(li, half)
    right = merge_sort(tmp, count-half)
    return merge(left, right)


def merge(x, y):
    if not x: return y
    if not y: return x
    if x.val < y.val:
        head, x = x, x.next
    else:
        head, y = y, y.next
    head.next = merge(x, y)
    return head