[数据结构与算法]leetcode 148. 排序链表 python

题目描述：

?

题解一（通过）：

采用归并排序，归并排序算法可以参考：

归并排序算法_ganggang的博客-CSDN博客

1.sortList函数：

? <1>如果head为空或head.next为空，则直接返回，对用归并排序中已经划分到单个数字的情况。

? <2>否则先确定链表长度length，将链表划分为左右两部分。

? <3>对lefthalf right分别调用sortList继续划分。

? <4>对划分完成的righthalf righthalf调用merge函数进行归并。

2.merge函数

? <1>创建一个ListNode res。

? <2>从left right第一个节点开始进行比较，将val较小的加入res。

? <3>当left right两者有一个为空时，直接将剩下的一个加入res。

class Solution(object):
    def sortList(self, head):
        if head == None or head.next == None:
            return head
        length = 0
        cur = head
        while cur:
            length = length + 1
            cur = cur.next
        mid = length // 2
        cur = head
        for i in range(mid - 1):
            cur = cur.next

        righthead = cur.next
        cur.next = None
        lefthead = head
        lefthalf = self.sortList(lefthead)
        righthalf = self.sortList(righthead)

        def merge(left, right):
            res = ListNode()
            cur = res
            while left and right:
                if left.val <= right.val:
                    cur.next = left
                    left = left.next
                else:
                    cur.next = right
                    right = right.next
                cur = cur.next
            cur.next = left or right
            return res.next

        return merge(lefthalf, righthalf)?

?题解二（通过）：

采用最傻的办法，先把链表中所有节点的值保存在一个数组中，然后对数组进行排序，在排序后的数组的基础上创建链表。

class Solution(object):
    def sortList(self, head):
        numlist = []
        cur = head
        while cur:
            numlist.append(cur.val)
            cur =cur.next
        numlist = sorted(numlist)
        res = ListNode()
        cur = res
        for num in numlist:
            node = ListNode(val=num)
            cur.next = node
            cur = cur.next
        return res.next

?

?

?

?