PU Sort List

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* sortList(struct ListNode* head) {
    if (!head) return 0;
    if (!head->next) return head;
    struct ListNode *l = head, *r = head->next, dummy;
    while (r && r->next) {
        l = l->next;
        r = r->next->next;
    }
    r = l->next;
    l->next = 0;
    l = sortList(head);
    r = sortList(r);
    head = &dummy;
    while (l && r) {
        if (l->val < r->val) {
            head->next = l;
            l = l->next;
        }
        else {
            head->next = r;
            r = r->next;
        }
        head = head->next;
    }
    head->next = l ? l : r;
    return dummy.next;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *merge(struct ListNode *A, struct ListNode *B, struct ListNode *head) {
    while (A && B) {
        if (A->val < B->val) {
            head->next = A;
            A = A->next;
        }
        else {
            head->next = B;
            B = B->next;
        }
        head = head->next;
    }
    head->next = A ? A : B;
    while (head->next) head = head->next;
    return head;
}
struct ListNode *find(struct ListNode *head, int len) {
    while (head && --len) head = head->next;
    if (!head) return 0;
    struct ListNode *res = head->next;
    head->next = 0;
    return res;
}
struct ListNode* sortList(struct ListNode* head) {
    struct ListNode dummy, *p = head;
    dummy.next = head;
    int len = 0;
    while (p) {
        len++;
        p = p->next;
    }
    int i;
    for (i = 1; i < len; i <<= 1) {
        struct ListNode *cur = dummy.next;
        struct ListNode *tail = &dummy;
        while (cur) {
            struct ListNode *left = cur;
            struct ListNode *right = find(cur, i);
            cur = find(right, i);
            tail = merge(left, right, tail);
        }
    }
    return dummy.next;
}

# 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 not head or not head.next: return head
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        fast = self.sortList(slow.next)
        slow.next = None
        slow = self.sortList(head)
        def merge(l1, l2):
            cur = dummy = 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 if l1 else l2
            return dummy.next
        return merge(slow, fast)

# 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 not head or not head.next: return head

        count = 0
        cur = head
        while cur:
            cur = cur.next
            count += 1

        dummy = ListNode(0)
        dummy.next = head

        def find(dummy, i):
            cur = dummy
            while cur.next and i:
                cur = cur.next
                i -= 1
            return dummy.next, cur

        def merge(l1, l2):
            cur = dummy = 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 if l1 else l2
            while cur.next:
                cur = cur.next
            return dummy.next, cur

        i = 1
        while i < count:
            cur = dummy
            while cur.next:
                l_head, l_tail = find(cur, i)
                r_head, r_tail = find(l_tail, i)
                l_tail.next = None
                tmp = r_tail.next
                r_tail.next = None
                cur.next, tail = merge(l_head, r_head)
                tail.next = tmp
                cur = tail
            i *= 2
        return dummy.next