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

public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null ) return head;
        ListNode slow = head, fast = head, prev = null;
        while (fast != null && fast.next != null) {
            prev = slow; // use prev to preserve the node before mid node
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode left = head;
        ListNode right = slow;
        prev.next = null; // clear the end of left part, this is why we need prev
        ListNode sortedLeft = sortList(left);
        ListNode sortedRight = sortList(right);
        return merge(sortedLeft, sortedRight);
    }


    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        curr.next = l1 == null ? l2 : l1;
        return dummy.next;
    }
}

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        if not head or not head.next:
            return head
        prev = slow = fast = head
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        prev.next = None
        return self.merge_left_right(self.sortList(head), self.sortList(slow))

    def merge_left_right(self, left, right):
        curr = dummy = ListNode(0)
        while left and right:
            if left.val < right.val:
                curr.next = left
                left = left.next
            else:
                curr.next = right
                right = right.next
            curr = curr.next
        curr.next = left or right
        return dummy.next