11 - Hard - 链表排序

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4
示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

思路1，递归将链表一分为二，然后再合并，转为合并有序链表问题

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:  
            return head  
        prenode = head  
        p1 = prenode  
        p2 = prenode  
        l = 0  
        while p1:  
            l += 1  
            p1 = p1.next  
        mid = l/2  
        k = 0  
        l1 = prenode  
        while p2: # 将单链表从中间一分为二  
            if k >= mid-1:  
                tmp = p2.next  
                p2.next = None  
                l2 = tmp  
                break  
            else:  
                p2 = p2.next  
                k += 1  
        t1 = self.sortList(l1)  
        t2 = self.sortList(l2)  
        return self.mergeTwoLists(t1,t2) 
        
    def mergeTwoLists(self, l1, l2):#合并两个有序的链表  
        if not l1:  
            return l2  
        if not l2:  
            return l1  
        prenode = ListNode(1)  
        p = prenode  
        while l1 and l2:  
            if l1.val <= l2.val:  
                p.next = l1  
                l1 = l1.next  
            else:  
                p.next = l2  
                l2 = l2.next  
            p = p.next  
        if l1:  
            p.next = l1  
        if l2:  
            p.next = l2  
        return prenode.next  

思路2，将所有值复制到list里，然后将list排序，然后顺序给链表赋新值

f1 = head
        if f1 == None or f1.next == None:
            return head
        a = []
        while f1:
            a.append(f1.val) 
            f1 = f1.next
        a = sorted(a)
        
        f1 = head
        for x in a:
            f1.val = x
            f1 = f1.next
        return head