Sort List

Description

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

Example
Given 1->3->2->null, sort it to 1->2->3->null.

Challenge:
Solve it by merge sort & quick sort separately.

Link

Lintcode_ladder

Method

1. merge sort
2. x

Example

1. 1

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: You should return the head of the sorted linked list,
                    using constant space complexity.
     */
    ListNode *sortList(ListNode *head) {
        // write your code here
        if (!head || !head->next) {
            return head;
        }
        // get middle node
        ListNode* mid = getmiddle(head);
        // sort second part
        ListNode* right = sortList(mid->next);
        // disconnect first and second part
        mid->next = nullptr;
        // sort first part
        ListNode* left = sortList(head);
        // merge two sorted list into one sorted list
        return merge(left, right);    
    }
private:
    // standard get middle
    ListNode* getmiddle(ListNode* head) {
        if (!head) {
            return nullptr;
        }
        ListNode* slow = head;
        // make sure the middle is the perfect middle pos or left one
        ListNode* fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    // standard merge
    ListNode* merge(ListNode* h1, ListNode* h2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while (h1 && h2) {
            if (h1->val < h2->val) {
                tail->next = h1;
                h1 = h1->next;
            } else {
                tail->next = h2;
                h2 = h2->next;
            }
            tail = tail->next;
        }
        if (h1) {
            tail->next = h1;
        } else {
            tail->next = h2;
        }
        return dummy.next;
    }
};

Similar problems

x

Tags

x