Sort linked list (in Python)

Problem

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Solution

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
 
class Solution(object):
    def merge(self, l1, l2) :
 
        fast = l1
        slow = l2
 
        dummy = ListNode(0)
        head = dummy
 
        while fast and slow :
            if fast.val < slow.val :
                dummy.next = fast
                dummy = dummy.next
                fast = fast.next
            else :
                dummy.next = slow
                slow = slow.next
                dummy = dummy.next
 
        dummy.next = fast or slow
        return head.next
 
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
 
        if head == None or head.next == None :
            return head
 
        slow = head
        fast = head.next
 
        if head.next != None: 
            
            while fast and fast.next :
                fast = fast.next.next
                slow = slow.next
 
            start = slow.next
            slow.next = None
 
            l1 = self.sortList(head)
            l2 = self.sortList(start)
 
            return self.merge(l1, l2)

Source

https://leetcode.com/problems/sort-list/