题解 | #单链表的排序#

遍历链表的值用数组保存，然后修改链表的数值

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

#
# 
# @param head ListNode类 the head node
# @return ListNode类
#
class Solution:
    def sortInList(self , head ):
        # write code here
        if head is None or head.next is None:
            return head
        vals = []
        p = head
        while p:
            vals.append(p.val)
            p = p.next
        vals = sorted(vals)
        p = head
        for val in vals:
            p.val = val
            p = p.next
        return head

归并排序超时

class Solution:
    def sortInList(self , head ):
        # write code here
        if head is None or head.next is None:
            return head
        slow = head
        fast = head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next
        new_list = slow.next
        slow.next = None
        left = self.sortInList(head)
        right = self.sortInList(new_list)
        dummy = ListNode(0)
        p = dummy
        while left and right:
            if left.val < right.val:
                p.next = left
                left = left.next
            else:
                p.next = right
                right = right.next
            p = p.next
        p.next = left if left is not None else right
        return dummy.next