Sort List

问题描述:

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

解决代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode *first = head, *second = head->next, *mid= NULL;
        while(second->next != NULL && second->next->next != NULL){       // find the mid position
            first = first->next;
            second = second->next->next;
        }
        mid = first->next;
        first->next = NULL;
        ListNode *left = sortList(head);
        ListNode *right = sortList(mid);
        return MergeSort(left, right);
    }
    ListNode* MergeSort(ListNode *left, ListNode*right){
        ListNode* newNode = new ListNode(0);                             //
        ListNode* p = newNode;
        while(left != NULL && right != NULL){
            if(left->val <= right->val){
                p->next = left;
                p = p->next;
                left = left->next;
            }else{
                p->next = right;
                p = p->next;
                right = right->next;
            }
        }
        if(left != NULL)
            p->next = left;
        if(right != NULL)
            p->next = right;
        return newNode->next;
    }
};

有人采取自底向上的策略,给出了非递归解法,时间O(nlgn) 空间O(1):

/**
 * Merge sort use bottom-up policy,
 * so Space Complexity is O(1)
 * Time Complexity is O(NlgN)
 * stable sort
*/
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if(!head || !(head->next)) return head;
        //get the linked list's length
        ListNode* cur = head;
        int length = 0;
        while(cur){
            length++;
            cur = cur->next;
        }
        ListNode dummy(0);
        dummy.next = head;
        ListNode *left, *right, *tail;
        for(int step = 1; step < length; step <<= 1){
            cur = dummy.next;
            tail = &dummy;
            while(cur){
                left = cur;
                right = split(left, step);
                cur = split(right,step);
                tail = merge(left, right, tail);
            }
        }
        return dummy.next;
    }
private:
    /**
     * Divide the linked list into two lists,
     * while the first list contains first n ndoes
     * return the second list's head
     */
    ListNode* split(ListNode *head, int n){
        //if(!head) return NULL;
        for(int i = 1; head && i < n; i++) head = head->next;
        if(!head) return NULL;
        ListNode *second = head->next;
        head->next = NULL;
        return second;
    }
    /**
      * merge the two sorted linked list l1 and l2,
      * then append the merged sorted linked list to the node head
      * return the tail of the merged sorted linked list
     */
    ListNode* merge(ListNode* l1, ListNode* l2, ListNode* head){
        ListNode *cur = head;
        while(l1 && l2){
            if(l1->val > l2->val){
                cur->next = l2;
                cur = l2;
                l2 = l2->next;
            }
            else{
                cur->next = l1;
                cur = l1;
                l1 = l1->next;
            }
        }
        cur->next = (l1 ? l1 : l2);
        while(cur->next) cur = cur->next;
        return cur;
    }
};

https://leetcode.com/discuss/28594/bottom-recurring-with-space-complextity-time-complextity

Leave a Reply

Your email address will not be published. Required fields are marked *