148.-sort-list.md

148. Sort List

{% tabs %} {% tab title="Python-new" %}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        ## 一开始就想到最简单的，变成array 
        ## logn 那就是二分 
        
        ### [4,2,1,3]
        
        if not head or not head.next:
            return head
        ## 
        slow = head
        fast = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
            
        mid = slow.next
        slow.next = None
        l = self.sortList(head)
        r = self.sortList(mid)
        return self.merge(l,r)
        
    
    def merge(self,node1, node2):
        
        ## 不能搞dummy 
        # dummy = ListNode(-1)
        # dummy.next = 
        
        if not node1 or not node2:
            return node2 or node1
        if node1.val > node2.val:
            node1, node2 = node2, node1
            
        head = node =  node1
        node1 = node1.next
        ## 
        while node1 and node2:
            
            if node1.val >= node2.val:
                node.next = node2
                node2 = node2.next
                node = node.next
                
            else:
                node.next = node1
                node1 = node1.next
                node = node.next
                
        if node1:
            node.next = node1
        elif node2:
            node.next = node2
            
        return head

{% endtab %}

{% tab title="Python-old" %}

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

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        # divide list into two parts
        fast, slow = head.next, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        second = slow.next
        # cut down the first part
        slow.next = None
        l = self.sortList(head)
        r = self.sortList(second)
        return self.merge(l, r)

    # merge in-place without dummy node        
    def merge(self, l, r):
        if not l or not r:
            return l or r
        if l.val > r.val:
            l, r = r, l
        # get the return node "head"
        head = pre = l
        l = l.next
        while l and r:
            if l.val < r.val:
                l = l.next
            else:
                nxt = pre.next
                pre.next = r
                tmp = r.next
                r.next = nxt
                r = tmp
            pre = pre.next
        # l and r at least one is None
        pre.next = l or r
        return head

            
        

{% endtab %} {% endtabs %}