2015年9月8日星期二

Lintcode: Sort List

Sort a linked list in O(n log n) time using constant space complexity.
Have you met this question in a real interview? 
Yes
Example
Given 1-3->2->null, sort it to 1->2->3->null.
Tags Expand 
Linked List


Solution:
It is based on the problem of merged two linked lists.
reference thoughts: http://blog.csdn.net/linhuanmars/article/details/21133949
reference codes: http://siddontang.gitbooks.io/leetcode-solution/content/linked_list/sort_list.html

p.s. quicksort is not convenient for linkedlist

Note: the whileloop condition (Line 29) cannot be changed to (fast && fast->next). In this case, the fast pointer may point to NULL. Slow pointer will point to the right side of the midpoint if number of lists is even.
e.g. if the list has two nodes, the slow points to the second node while fast points to NULL

Time: O(nlogn)
Space: O(n)    only one branch at one time   --see wikipedia

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
 * 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) {
        //division stop condition
        if(head == NULL || head->next == NULL){
            return head;
        }
        //only start divide if the input list has more than two nodes
        ListNode *slow = head;
        ListNode *fast = head;
        //remember this while loop condition 
        while(fast->next && fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        //Break the input list
        fast = slow->next;
        slow->next = NULL;
        
        ListNode* p1 = sortList(head);
        ListNode* p2 = sortList(fast);
        
        return merge(p1, p2);
        
    }
    
    //combine two sorted lists and return the head of the combined list
    ListNode *merge(ListNode* l1, ListNode* l2){
        if(!l1) {
            return l2;
        }else if (!l2){
            return l1;
        }
        ListNode *dummy = new ListNode(-1);
        ListNode *cur = dummy;
        while(l1 && l2){
            if(l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            }else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if (l1) {
            cur->next = l1;
        }else if(l2){
            cur->next = l2;
        }
        
        return dummy->next;
    }
};

Lintcode second:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * 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 == NULL) return head;
        if(!head->next) return head;
        ListNode *p1, *p2;
        p1 = p2 = head;
        while(p2->next && p2->next->next){
            p1 = p1->next;
            p2 = p2->next->next;
        }
        p2 = p1->next;
        p1->next = NULL;
        p1 = head;
        
        ListNode* left = sortList(p1);
        ListNode* right = sortList(p2);
        return merge(left, right);
    }
    ListNode *merge(ListNode *left, ListNode *right){
        ListNode *dummy = new ListNode(0);
        ListNode *head = dummy;
        while(left && right){
            if(left->val <= right->val){
                dummy->next = left;
                left = left->next;
            }else{
                dummy->next = right;
                right = right->next;
            }
            dummy = dummy->next;
        }
        if(left) dummy->next = left;
        if(right) dummy->next = right;
        head = head->next;
        return head;
    }
};
发帖者 时间：

没有评论:

发表评论

订阅： 博文评论 (Atom)