148.md

Sort List

Description

link

---

Solution

See Code

Recursively Sorted

---

Code

O(nlogn)

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

class Solution:
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        second = slow.next
        slow.next = None # Cut down the first part
        l = self.sortList(head)
        r = self.sortList(second)
        return self.merge(l, r)
    
    # Sort in-place
    def merge(self, l, r):
        if not l or not r:
            return l or r
        
        if l.val > r.val:
            l, r = r, l
        
        pre = head = l
        l = l.next
        while l and r:
            if l.val < r.val:
                pre.next = l
                l = l.next
            else:
                pre.next = r
                r = r.next
            pre = pre.next
        pre.next = l if l else r
        return head