My accepted Python solution using merge sort.


  • 1
    B
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        # @param {ListNode} head
        # @return {ListNode}
        def sortList(self, head):
            size, node = 0, head
            while node:
                node = node.next
                size += 1
            return self.merge_sort(head, size)
    
        def merge_sort(self, head, size):
            if size <= 1:
                return head
    
            right = prev = head
            left_size = size/2
            right_size = size - left_size
    
            for i in range(left_size):
                prev = right
                right = right.next
            prev.next = None  # divide list to two part
    
            left = self.merge_sort(head, left_size)
            right = self.merge_sort(right, right_size)
            return self.merge(left, right)
    
        def merge(self, l1, l2):
            vhead = curr = ListNode(0)
            while l1 and l2:
                if l1.val <= l2.val:
                    curr.next = l1
                    l1 = l1.next
                else:
                    curr.next = l2
                    l2 = l2.next
                curr = curr.next
            curr.next = l1 or l2
            return vhead.next

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.