Sort List Bottom-Up — O(1) Space Merge Sort

# Python
def sortList(head):
    # Count length
    n = 0; cur = head
    while cur: n += 1; cur = cur.next

    dummy = ListNode(0, head)
    size = 1
    while size < n:
        cur = dummy.next
        tail = dummy
        while cur:
            left = cur
            right = split(left, size)
            cur = split(right, size)
            merged, merged_tail = merge(left, right)
            tail.next = merged
            tail = merged_tail
        size <<= 1
    return dummy.next

def split(head, n):
    # Advance n-1 steps, cut and return the rest.
    for _ in range(n-1):
        if head: head = head.next
    if not head: return None
    rest = head.next; head.next = None; return rest

def merge(l1, l2):
    dummy = cur = ListNode(0)
    while l1 and l2:
        if l1.val <= l2.val: cur.next = l1; l1 = l1.next
        else: cur.next = l2; l2 = l2.next
        cur = cur.next
    cur.next = l1 or l2
    while cur.next: cur = cur.next
    return dummy.next, cur

// Java
public ListNode sortList(ListNode head) {
    int n = 0; ListNode cur = head;
    while (cur != null) { n++; cur = cur.next; }
    ListNode dummy = new ListNode(0, head);
    for (int size = 1; size < n; size <<= 1) {
        cur = dummy.next; ListNode tail = dummy;
        while (cur != null) {
            ListNode left = cur, right = split(left, size);
            cur = split(right, size);
            ListNode[] merged = merge(left, right);
            tail.next = merged[0]; tail = merged[1];
        }
    }
    return dummy.next;
}
ListNode split(ListNode head, int n) {
    for (int i = 1; i < n && head != null; i++) head = head.next;
    if (head == null) return null;
    ListNode rest = head.next; head.next = null; return rest;
}
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;
    while (cur.next != null) cur = cur.next;
    return new ListNode[]{dummy.next, cur};
}