Sort List — Top-Down Merge Sort

# Python
def sortList(head):
    if not head or not head.next: return head
    # Find middle and split
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next; fast = fast.next.next
    mid = slow.next; slow.next = None
    # Sort both halves
    left = sortList(head)
    right = sortList(mid)
    # Merge
    dummy = cur = ListNode(0)
    while left and right:
        if left.val <= right.val: cur.next = left; left = left.next
        else: cur.next = right; right = right.next
        cur = cur.next
    cur.next = left or right
    return dummy.next

// Java
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
    ListNode mid = slow.next; slow.next = null;
    return merge(sortList(head), sortList(mid));
}
ListNode merge(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), cur = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; }
        else { cur.next = l2; l2 = l2.next; }
        cur = cur.next;
    }
    cur.next = l1 != null ? l1 : l2;
    return dummy.next;
}