这题一开始想新建一个list，结果MLE了，后来想了想不用新建，insertion的概念理解好就行，具体编程部分不难
1
/*
*
2
* Definition for singly-linked list.
3
* struct ListNode {
4
* int val;
5
* ListNode *next;
6
* ListNode(int x) : val(x), next(NULL) {}
7
* };
8
*/
9
class
Solution {
10
public
:
11
ListNode *insertionSortList(ListNode *
head) {
12
if
(!head)
return
NULL;
13
ListNode *hpre =
new
ListNode(
0
);
14
hpre->next =
head;
15
ListNode *pre =
head;
16
head = head->
next;
17
while
(head) {
18
if
(head->val > pre->
val) {
19
head = head->
next;
20
pre = pre->
next;
21
}
22
else
{
23
pre->next = head->
next;
24
ListNode *tmp =
hpre;
25
while
(head->val > tmp->next->val) tmp = tmp->
next;
26
head->next = tmp->
next;
27
tmp->next =
head;
28
head = pre->
next;
29
}
30
}
31
return
hpre->
next;
32
}
33
};
C#
1
/*
*
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* public int val;
5
* public ListNode next;
6
* public ListNode(int x) { val = x; }
7
* }
8
*/
9
public
class
Solution {
10
public
ListNode InsertionSortList(ListNode head) {
11
if
(head ==
null
)
return
null
;
12
ListNode hpre =
new
ListNode(
0
);
13
hpre.next =
head;
14
ListNode pre =
head;
15
head =
head.next;
16
while
(head !=
null
) {
17
if
(head.val >
pre.val) {
18
head =
head.next;
19
pre =
pre.next;
20
}
21
else
{
22
pre.next =
head.next;
23
ListNode tmp =
hpre;
24
while
(head.val > tmp.next.val) tmp =
tmp.next;
25
head.next =
tmp.next;
26
tmp.next =
head;
27
head =
pre.next;
28
}
29
}
30
return
hpre.next;
31
}
32
}
