Cacher is the code snippet organizer for pro developers

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

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None or head.next == None:
            return head
        slow = head
        fast = head
        while fast.next != None and fast.next.next != None:
            slow = slow.next
            fast = fast.next.next
        fast = slow.next
        slow.next = None
        # If we just assume that the p1,p2 are the sorted lists,
        # then we can came up with the conclusion that the algo with return sorted list.
        p1 = self.sortList(head)
        p2 = self.sortList(fast)
        return self.merge(p1, p2)
    def merge(self, list1, list2):
        dummy = ListNode(0)
        p = dummy
        while list1 and list2:
            if list1.val <= list2.val:
                p.next = list1
                list1 = list1.next
            else:
                p.next = list2
                list2 = list2.next
            p = p.next
        if not list1:
            p.next = list2
        if not list2:
            p.next = list1
        return dummy.next

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

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