Algorithm

LintCode/Sort List

Problem Summary

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

Solution

I tried merge sort and quick sort. The merge sort worked perfectly, but the quick sort got TLE(time limit exceeded) for some cases.

When the given list is already ascending or almost in order, the time complexity of quick sort would grow to O(N^2). I haven’t found a way to optimize it yet. If you have any suggestions or would like to discuss with me, please leave a comment or email me, thanks in advance!

Code 1 - Merge Sort 1

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
class ListNode {
 public:
     int val;
     ListNode *next;
     ListNode(int val) {
         this->val = val;
         this->next = NULL;
    }
};
class Solution {
public:
    /*
     * @param head: The head of linked list.
     * @return: You should return the head of the sorted linked list, using constant space complexity.
     */
	ListNode * merge(ListNode *l,ListNode *r)
	{
		if (l == NULL)
			return r;
		if (r == NULL)
			return l;
		if (l->val < r->val)
		{
			l->next = merge(l->next,r);
			return l;
		}
		else
		{
			r->next = merge(l,r->next);
			return r;
		}
	}
    ListNode * sortList(ListNode * head) {
        if (head == NULL || head->next == NULL)
        	return head;
        
        ListNode *pre = head, *l = head, *r = head;
		while (r != NULL && r->next != NULL)
		{
			pre = l;
			l = l->next;
			r = r->next->next;
		}
		pre->next = NULL;
		return merge(sortList(head),sortList(l));
    }
};

Code 2 - Merge Sort 2

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
89
90
91
92
93
94
95
/**
 * 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 head of linked list.
     * @return: You should return the head of the sorted linked list, using constant space complexity.
     */
	void set_free(ListNode *p)
	{
		if (p==NULL)
			return;
		set_free(p->next);
		delete p;
	}
	ListNode * merge(ListNode *l,ListNode *r)
	{
		ListNode *p = l, *q = r;
		ListNode *res = new ListNode(0);
		ListNode *head = res;
		
		while (p!= NULL && q!= NULL)
		{
			if (p->val < q->val)
			{
				res->next = new ListNode(p->val);
				p = p->next;
			}
			else
			{
				res->next = new ListNode(q->val);
				q = q->next;
			}
			res = res->next;
		}
		while (p!=NULL)
		{
			res->next = new ListNode(p->val);
			res = res->next;
			p = p->next;
		}
		while (q!=NULL)
		{
			res->next = new ListNode(q->val);
			res = res->next;
			q = q->next;
		}
		set_free(l);
		set_free(r);
		return head->next;
	}
	ListNode * merge_sort(ListNode *head,int n)
	{
		if (n<=1)
			return head;
		ListNode *pre = head, *mid = head;
		for (int i = 0; i < n/2; ++i)
		{
			pre = mid;
			mid = mid->next;
		}
		pre->next = NULL;
		ListNode *l = merge_sort(head,n/2);
		ListNode *r = merge_sort(mid,n-n/2);
		return merge(l,r);
	}
    ListNode * sortList(ListNode * head) {
        int n = 0;
        if (head == NULL)
        	return 0;
        ListNode *p = head;
        while (p)
        {
        	++n;
        	p = p->next;
        }
        return merge_sort(head,n);
    }
};

Code 3 - Quick Sort

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
class Solution {
public:
    /*
     * @param head: The head of linked list.
     * @return: You should return the head of the sorted linked list, using constant space complexity.
     */
	void set_list_free(ListNode * head)
	{
		if (head == NULL)
			return;
		set_list_free(head->next);
		delete head;
	}
    ListNode * sortList(ListNode * head) {
        int n = 0;
        if (head == NULL || head->next == NULL)
        	return head;
        int v = head->val;
        ListNode *left = new ListNode(0);
        ListNode *right = new ListNode(0);
        ListNode *p = left, *q = right;
        ListNode *cur = head->next;
       	while(cur)
       	{
       		if (cur->val < v)
       		{
       			p->next = new ListNode(cur->val);
       			p = p->next;
       		}
       		else
       		{
       			q->next = new ListNode(cur->val);
       			q = q->next;
       		}
       		cur = cur->next;
       	}
       	set_list_free(head);
       	cur = sortList(left->next);
       	delete left;
       	left = cur;
       	cur = sortList(right->next);
       	delete right;
       	right = new ListNode(v);
		right->next = cur;
       	if (left == NULL)
       		return right;
        ListNode *pre = left;
        cur = left;
        while (cur)
        {
        	pre = cur;
        	cur = cur->next;
        }
       	pre->next = right;
        
        return left;
    }
};