LeetCode - Sort List

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

排序一个单向链表，要求时间复杂度O(nlgn)，空间复杂度O(1)。使用merge sort解该问题，网上的答案用的都是递归的解法，也就是top-down的实现，空间复杂度应该为O(lgn)，并不是常数，使用bottom-up的实现可以达到O(1)的空间复杂度。

wikipedia只给出了数组的top-down & bottom-up实现和list的top-down实现。
这里的快慢指针技巧非常有用：link1 link2。
链表的实现有带头节点和不带头节点两种形式，不带头节点的实现需要判断head==NULL的情况，带头节点则会浪费一个节点的空间。对于不带头节点的链表，各个操作可以用二级指针实现，把代码书写上的复杂度转移到coder的脑袋里。

Talk is cheap, show you the code:

两个bottom-up的实现，第一个空间复杂度O(n)，最多需要存储n/2个链表头指针。

Code 1.

这里的queue使用list会超时。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 **/
#include <deque>

using namespace std;

class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if (head == NULL) {
            return NULL;
        }   

        deque<ListNode*> queue;
        ListNode* iter = head;
        ListNode* next = NULL;
        while (iter != NULL) {
            queue.push_back(iter);
            next = iter->next;
            iter->next = NULL;
            iter = next;
        }   
        while (queue.size() >= 2) {
            iter = queue.front();
            queue.pop_front();
            next = queue.front();
            queue.pop_front();
            queue.push_back(mergeList(iter, next));
        }   
        return queue.front();   
    }   

private:
    ListNode* mergeList(ListNode* left, ListNode* right) {
        ListNode* merged_list = NULL;
        ListNode** next_holder = &merged_list;
        ListNode* selected_node = NULL;
        while(left != NULL && right != NULL) {
            if (left->val <= right->val) {
                selected_node = left;
                left = left->next;
            } else {
                selected_node = right;
                right = right->next;
            }   
            selected_node->next = NULL;
            *next_holder = selected_node;
            next_holder = &(selected_node->next);
        }
        *next_holder = left ? left : right;
        return merged_list;
    }
};

Code 2.

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        //assert(head != NULL);

        int step = 1;
        int len = length(head);
        ListNode* sorted_list = NULL;
        ListNode** tail_holder = &sorted_list;
        while (step < len) {
            ListNode* left_head = NULL;
            ListNode* left_tail = NULL;
            ListNode* right_head = NULL;
            ListNode* right_tail = NULL;

            cutList(head, step, &left_head, &left_tail, &head);
            left_tail->next = NULL;
            if (head == NULL) {
                *tail_holder = left_head;
                goto NEXT_LOOP;
            }   

            cutList(head, step, &right_head, &right_tail, &head);
            right_tail->next = NULL;
            *tail_holder = mergeList(left_head, right_head);
            //assert( (left_tail->next == NULL && right_tail->next != NULL)
            //        || (left_tail->next != NULL && right_tail->next == NULL));
            if (right_tail->next == NULL) {
                tail_holder = &(right_tail->next);
            } else {
                tail_holder = &(left_tail->next);
            }   
NEXT_LOOP:
            if (head == NULL) {
                head = sorted_list;
                sorted_list = NULL;
                tail_holder = &sorted_list;
                step *= 2;
            }   
        }   
        return head;
    }   


private:
    int length(ListNode* head) {
        int len = 0;
        while (head != NULL) {
            ++len;
            head = head->next;
        }   
        return len;
    }   
    void cutList(ListNode* head, int len,
            ListNode** p_left_head, ListNode** p_left_tail, ListNode** p_right_head) {
        //assert(head != NULL);

        *p_left_head = head;
        *p_left_tail = head;
        *p_right_head = head->next;
        for (int i = 0; i < len && head != NULL; ++i) {
            *p_left_tail = head;
            *p_right_head = head->next;
            head = head->next;
        }
    }
    ListNode* mergeList(ListNode* left, ListNode* right) {
        //assert(left != NULL);
        //assert(right != NULL);

        ListNode* merged_list = NULL;
        ListNode** next_holder = &merged_list;
        ListNode* selected_node = NULL;
        while(left != NULL && right != NULL) {
            if (left->val <= right->val) {
                selected_node = left;
                left = left->next;
            } else {
                selected_node = right;
                right = right->next;
            }
            selected_node->next = NULL;
            *next_holder = selected_node;
            next_holder = &(selected_node->next);
        }
        *next_holder = left ? left : right;
        return merged_list;
    }
};