https://leetcode-cn.com/explore/interview/card/bytedance/244/linked-list-and-tree/1040/

image.png

要求用O(nlogn)复杂度的排序，只有归并比较适合
在归并中注意递归的merge的时机
在链表一分为二的时候，用一个慢节点和快节点跑步来找
代码如下：

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        p = head
        p2 = p.next.next
        while p2:
            if not p2.next or not p2.next.next:
                break
            p = p.next
            p2 = p2.next.next
        p_right = p.next
        p.next = None
        left = self.sortList(head)
        right = self.sortList(p_right)
        return self.mergeList(left,right)
        
        
    
    def mergeList(self,l1,l2):
        if not l1:
            return l2
        if not l2:
            return l1
        new_list = None
        head = None
        while l1 and l2:
            tmp_node = l1
            if l1.val>l2.val:
                tmp_node = l2
                l2 = l2.next
            else:
                l1 = l1.next
            if not new_list:
                new_list = ListNode(tmp_node.val)
                head = new_list
            else:
                next_node = ListNode(tmp_node.val)
                new_list.next = next_node
                new_list = next_node
        if l1:
            new_list.next = l1
        if l2:
            new_list.next = l2
            
        return head