forked from fanfank/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
insertion-sort-list.cpp
70 lines (69 loc) · 2.05 KB
/
insertion-sort-list.cpp
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
/*************************************************************
Solution 1: Used second level pointer, better than solution 2
*************************************************************/
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
ListNode **pHead = &head, **p = &head, **pp = NULL;
while(*p) {
pp = pHead;
while((*pp)->val <= (*p)->val && pp != p)
pp = &((*pp)->next);
if(pp != p) {
ListNode *tmp = *pp;
*pp = *p;
*p = (*p)->next;
(*pp)->next = tmp;
continue;
}
p = &((*p)->next);
}
return *pHead;
}
};
/*************************************************************
Solution 2: traditional textbook's method, easy to understand
*************************************************************/
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
ListNode *p = head, *pp = NULL;
while(p && p->next) {
if(p->next->val < head->val) {
ListNode *tmp = p->next;
p->next = p->next->next;
tmp->next = head;
head = tmp;
continue;
}
pp = head;
while(pp->next->val <= p->next->val && pp->next != p->next)
pp = pp->next;
if(pp->next != p->next) {
ListNode *tmp = p->next;
p->next = p->next->next;
tmp->next = pp->next;
pp->next = tmp;
continue;
}
p = p->next;
}
return head;
}
};