Method sortList

Sorted/SortList.py:119–182

:type head: ListNode :rtype: ListNode

(self, head)

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        lists = []
        
        while head:
            lists.append(head.val)
            head = head.next
        
    
        def merge_sort(l, r):
            
            _l = 0
            _r = 0
            
            _l_length = len(l)
            _r_length = len(r)
            
            result = []
            
            while _l < _l_length and _r < _r_length:
                if l[_l] < r[_r]:
                    result.append(l[_l])
                    _l += 1
                else:
                    result.append(r[_r])
                    _r += 1
                    
            if _l == _l_length:
                while _r < _r_length:
                    result.append(r[_r])
                    _r += 1
            else:
                while _l < _l_length:
                    result.append(l[_l])
                    _l += 1
            
            return result
        
        def split(l):
            if len(l) <= 1:
                return l
            
            _l = split(l[:len(l)//2])
            _r = split(l[len(l)//2:])
            
            return merge_sort(_l, _r)
        
        lists = split(lists)
        
        if not lists:
            return None
        
        head = ListNode(lists[0])
        
        _head = head