148. Sort List

  • 27.7%

https://leetcode.com/problems/sort-list/?tab=Description

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


归并排序

微信面试题:使用快速排序,对链表进行排序

方法一:

归并排序

https://discuss.leetcode.com/topic/17150/clean-and-short-merge-sort-solution-in-c

Clean and short Merge sort Solution in c++

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
class Solution {
public:
ListNode* merge( ListNode* head1 , ListNode * head2){
ListNode* d = new ListNode (0); // dummy node
ListNode* e = d;
while(head1||head2){
if(head1 && (!head2 || head1->val <= head2 -> val) ){
e=e->next= head1 ;
head1 = head1 -> next;
}
if(head2 && (!head1 || head2->val < head1 -> val) ){
e=e->next= head2 ;
head2 = head2 -> next;
}
}
e->next = NULL;
return d->next;
}
ListNode* sortList(ListNode* head) {
if(!head || !head->next) return head;
ListNode* slow = head;
ListNode* fast =head->next;
while(fast && fast->next){ // to find middle node
fast= fast->next->next;
slow = slow->next;
}
ListNode* headb = slow->next; // headb is start of 2nd half of list
slow->next = NULL;
return merge(sortList(head) , sortList(headb));
}
};

我的代码实现:

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
class Solution {
public:
ListNode* sortList(ListNode* head) {
if(!head || !head->next) return head;
ListNode* fast = head, *slow = head;
while(fast->next && fast->next->next){
fast = fast->next->next;
slow = slow->next;
}
ListNode* tmp = slow->next;
slow->next = NULL;
ListNode* head1 = sortList(head);
ListNode* head2 = sortList(tmp);
ListNode* node = merge(head1, head2);
return node;
}

ListNode* merge(ListNode* head1, ListNode* head2){
if(head1==NULL) return head2;
if(head2==NULL) return head1;
if(head1->val<=head2->val){
head1->next = merge(head1->next, head2);
return head1;
}else{
head2->next = merge(head1, head2->next);
return head2;
}
}
};

方法二:

使用147题的插入排序,效率O(n^2)不能满足要求

超时

方法三:

归并排序

我的代码实现:

有bug

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
/**
* 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 || !head->next)
return head;
ListNode* slow = head, *fast = head;
while(fast->next && fast->next->next){
fast = fast->next->next;
slow = slow->next;
}
fast = slow->next;
slow->next = nullptr;
sortList(head);
sortList(fast);
return merge(head, fast);
}

ListNode* merge(ListNode* l1, ListNode* l2){
if(!l1)
return l2;
if(!l2)
return l1;
if(l1->val < l2->val){
l1->next = merge(l1->next, l2);
return l1;
}else{
l2->next = merge(l1, l2->next);
return l2;
}
}
};

cpp


https://discuss.leetcode.com/topic/10382/bottom-to-up-not-recurring-with-o-1-space-complextity-and-o-nlgn-time-complextity

Bottom-to-up(not recurring) with o(1) space complextity and o(nlgn) time complextity

this problem can be easily solved using recurrence and divide-and-conquer. But it consumes program stack to store the recurring function stack frame, actually it consumes o(lgn) space complexity. Recursion use up-to-bottom strategy , why not try the opposite way–bottom-to-up, luckily it works, it only consumes 0(1) space complexity and o(nlgn) time complextity.

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
/**
* 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://discuss.leetcode.com/topic/3085/my-o-n-log-n-time-o-1-space-solution

My O(n log n) time, O(1) space solution

Nice problem. I use a non-recurisve way to write merge sort.

For example, the size of ListNode is 8,

Round #1 block_size = 1

(a1, a2), (a3, a4), (a5, a6), (a7, a8)

Compare a1 with a2, a3 with a4 …

Round #2 block_size = 2

(a1, a2, a3, a4), (a5, a6, a7, a8)

merge two sorted arrays (a1, a2) and (a3, a4), then merge tow sorted arrays(a5, a6) and (a7, a8)

Round #3 block_size = 4

(a1, a2, a3, a4, a5, a6, a7, a8)

merge two sorted arrays (a1, a2, a3, a4), and (a5, a6, a7, a8)

No need for round #4 cause block_size = 8 >= n = 8

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
class Solution {
public:
int count_size(ListNode *node){
int n = 0;
while (node != NULL){
node = node->next;
++n;
}
return n;
}
ListNode *sortList(ListNode *head) {
int block_size = 1, n = count_size(head), iter = 0, i = 0, a = 0, b = 0;
ListNode virtual_head(0);
ListNode *last = NULL, *it = NULL, *A = NULL, *B = NULL, *tmp = NULL;
virtual_head.next = head;
while (block_size < n){
iter = 0;
last = &virtual_head;
it = virtual_head.next;
while (iter < n){
a = min(n - iter, block_size);
b = min(n - iter - a, block_size);

A = it;
if (b != 0){
for (i = 0; i < a - 1; ++i) it = it->next;
B = it->next;
it->next = NULL;
it = B;

for (i = 0; i < b - 1; ++i) it = it->next;
tmp = it->next;
it->next = NULL;
it = tmp;
}

while (A || B){
if (B == NULL || (A != NULL && A->val <= B->val)){
last->next = A;
last = last->next;
A = A->next;
} else {
last->next = B;
last = last->next;
B = B->next;
}
}
last->next = NULL;
iter += a + b;
}
block_size <<= 1;
}
return virtual_head.next;
}
};

python


https://discuss.leetcode.com/topic/30407/clean-python-code

Clean python code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def merge(self, h1, h2):
dummy = tail = ListNode(None)
while h1 and h2:
if h1.val < h2.val:
tail.next, tail, h1 = h1, h1, h1.next
else:
tail.next, tail, h2 = h2, h2, h2.next

tail.next = h1 or h2
return dummy.next

def sortList(self, head):
if not head or not head.next:
return head

pre, slow, fast = None, head, head
while fast and fast.next:
pre, slow, fast = slow, slow.next, fast.next.next
pre.next = None

return self.merge(*map(self.sortList, (head, slow)))

java


https://discuss.leetcode.com/topic/18100/java-merge-sort-solution

Java merge sort solution

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
public class Solution {

public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;

// step 1. cut the list to two halves
ListNode prev = null, slow = head, fast = head;

while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}

prev.next = null;

// step 2. sort each half
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);

// step 3. merge l1 and l2
return merge(l1, l2);
}

ListNode merge(ListNode l1, ListNode l2) {
ListNode l = new ListNode(0), p = l;

while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}

if (l1 != null)
p.next = l1;

if (l2 != null)
p.next = l2;

return l.next;
}

}

https://discuss.leetcode.com/topic/643/i-have-a-pretty-good-mergesort-method-can-anyone-speed-up-the-run-time-or-reduce-the-memory-usage

I have a pretty good MergeSort method. Can anyone speed up the run time or reduce the memory usage?

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
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode f = head.next.next;
ListNode p = head;
while (f != null && f.next != null) {
p = p.next;
f = f.next.next;
}
ListNode h2 = sortList(p.next);
p.next = null;
return merge(sortList(head), h2);
}
public ListNode merge(ListNode h1, ListNode h2) {
ListNode hn = new ListNode(Integer.MIN_VALUE);
ListNode c = hn;
while (h1 != null && h2 != null) {
if (h1.val < h2.val) {
c.next = h1;
h1 = h1.next;
}
else {
c.next = h2;
h2 = h2.next;
}
c = c.next;
}
if (h1 != null)
c.next = h1;
if (h2 != null)
c.next = h2;
return hn.next;
}
}

谢谢你,可爱的朋友。