题解 | 单链表的排序 | 链表排序

# 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 not head:
            return
        res=[]
        while head:
            res.append(head.val)
            head = head.next
        res.sort()
        a = ListNode(0)
        ans = a
        for r in res:
            a.next = ListNode(r)
            a = a.next
        return ans.next

class Solution:
    def sortInList(self , head ):
        if not head or  not head.next:
            return head
        
        cut = head
        
        slow = head
        fast = head
        # 查找中间节点
        while fast and fast.next:
            cut = slow
            slow = slow.next
            fast = fast.next.next
        left = head
        right = cut.next
        cut.next = None  # 断开左半个链表
        left = self.sortInList(left)
        right = self.sortInList(right)
        return self.merge(left, right)
        
    def merge(self, left, right):
        """合并两个已经排好序的链表"""
        guard = ListNode(0)
        p = guard
        while left and right:
            if left.val < right.val:
                guard.next = left
                left = left.next
            else:
                guard.next = right
                right = right.next
            guard = guard.next
        if left:
            guard.next = left
        if right:
            guard.next = right
        return p.next