leetcode_sort_list

发表于

难度：Medium

解题思路：可以快排，也可以归并排序。快排中加入了pivot_list，用来存储和pivot一样的值。

快排代码如下：

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/**
 * 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*pivot_head = head;
        ListNode*first_head = NULL;
        ListNode*second_head = NULL;

        Partition(pivot_head, first_head, second_head);
        if(first_head != NULL)
            first_head = sortList(first_head);
        if(second_head != NULL)
            second_head = sortList(second_head);
        ListNode *dummy = new ListNode(-22);
        ListNode *cur = dummy;
        if(first_head != NULL)
        {
            cur->next = first_head;
            cur = cur->next;
            while(cur->next != NULL)
            {
                cur = cur->next;
            }
        }
        if(pivot_head != NULL)
        {
            cur->next = pivot_head;
            cur=cur->next;
            while(cur->next != NULL)
            {
                cur = cur->next;
            }
        }
        cur->next = second_head;
        return dummy->next;
    }
    void Partition(ListNode * &pivot_head, ListNode * &first_head, ListNode * &second_head)
    {
        // cout<<"pivot:"<<pivot<<endl;
        if(pivot_head == NULL)
            return;
        ListNode *pivot_dummy = new ListNode(-22);
        ListNode *first_dummy = new ListNode(-1);
        ListNode *second_dummy = new ListNode(-11);
        
        pivot_dummy->next = pivot_head;
        int pivot = pivot_head->val;
        
        ListNode *pivot_cur = pivot_dummy;
        ListNode *first_cur = first_dummy;
        ListNode *second_cur = second_dummy;
        while(pivot_cur->next != NULL)
        {
            // cout<<"first_cur->next loop"<<endl;
            if(pivot_cur->next->val == pivot)
            {
                pivot_cur = pivot_cur->next;
            }
            else if(pivot_cur->next->val > pivot)
            {
                second_cur->next = pivot_cur->next;
                pivot_cur->next = pivot_cur->next->next;
                second_cur = second_cur->next;
                second_cur->next = NULL;
            }
            else if(pivot_cur->next->val < pivot)
            {
                first_cur->next = pivot_cur->next;
                pivot_cur->next = pivot_cur->next->next;
                first_cur = first_cur->next;
                first_cur->next = NULL;
            }
        }
        first_head = first_dummy->next;
        second_head = second_dummy->next;
        pivot_head = pivot_dummy->next;
    }
};

运行结果：49ms，超过74.88%

归并排序如下：

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
/**
 * 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 *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *slow = dummy;
        ListNode *fast = dummy;
        while(fast->next != NULL && fast->next->next != NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *new_head = slow->next;
        slow->next = NULL;
        ListNode *left_ = sortList(head);
        ListNode *right_ = sortList(new_head);
        return mergeSortedList(left_, right_);
    }
    ListNode* mergeSortedList(ListNode *left_head,ListNode *right_head)
    {
        ListNode *dummy =new ListNode(-1);
        ListNode *cur = dummy;
        ListNode *left_cur = left_head;
        ListNode *right_cur = right_head;
        while(left_cur != NULL && right_cur != NULL)
        {
            if(left_cur->val < right_cur->val)
            {
                cur->next = left_cur;
                left_cur = left_cur->next;
                cur = cur->next;
                cur->next = NULL;
            }
            else
            {
                cur->next = right_cur;
                right_cur = right_cur->next;
                cur = cur->next;
                cur->next = NULL;                
            }
        }
        if(left_cur != NULL)
        {
            cur->next = left_cur;
        }
        if(right_cur != NULL)
        {
            cur->next = right_cur;
        }
        return dummy->next;
    }
};

运行结果：59ms，超过27.49%