-
Notifications
You must be signed in to change notification settings - Fork 2
/
147.cpp
33 lines (32 loc) · 855 Bytes
/
147.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
/**
* 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 == NULL || head->next == NULL) return head;
ListNode *res = NULL, *pre = NULL, *cur = head, *r = head->next, *p;
while (cur != NULL) {
pre = NULL; p = res;
while (p != NULL && p->val < cur->val) {
pre = p;
p = p->next;
}
if (pre == NULL) {
cur->next = res;
res = cur;
} else {
pre->next = cur;
cur->next = p;
}
cur = r;
if (r != NULL) r = r->next;
}
return res;
}
};