forked from hongtaocai/code_interview
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathInsertionSortList.cpp
More file actions
38 lines (38 loc) · 931 Bytes
/
InsertionSortList.cpp
File metadata and controls
38 lines (38 loc) · 931 Bytes
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
/**
* 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) {
if(!head) {
return head;
}
ListNode dummy(0);
ListNode* dummyp = &dummy;
dummyp->next = head;
ListNode* p = dummyp->next;
while(p) {
ListNode* node = p->next;
if(!node) {
break;
}
if(node->val >= p->val) {
p = p->next;
} else {
ListNode* t = dummyp;
while(t->next->val < node->val) {
t = t->next;
}
p->next = node->next;
node->next = t->next;
t->next = node;
}
}
return dummyp->next;
}
};