LeetCode 147: Insertion Sort List
Sort a linked list using insertion sort.
代码
C语言版本：
21 / 21 test cases passed.
Status: Accepted
Runtime: 64 ms
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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* insertionSortList(struct ListNode* head) {
if ( !head ) {
return head;
}
struct ListNode* helper;
helper -> next = NULL;
struct ListNode* cur = head;
struct ListNode* behind = NULL;
struct ListNode* pre = helper;
while ( cur ) {
behind = cur -> next;
while ( pre -> next && pre->next->val < cur->val ) {
pre = pre -> next;
}
cur -> next = pre -> next;
pre -> next = cur;
pre = helper;
cur = behind;
}
return helper -> next;
}