147. Insertion Sort List
Sort ;a ;linked ;list ;using ;insertion ;sort.
用一个辅助指针来做表头避免处理改变head的时候的边界情况。
; ; ; ;<pre> ;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 ;== ;NULL){
13 ; ; ; ; ; ; ; ; ; ; ;return ;head;
14 ; ; ; ; ; ; ;}
15 ; ; ; ; ; ; ;
16 ; ; ; ; ; ; ;ListNode* ;helper ;= ;new ;ListNode(0);
17 ; ; ; ; ; ; ;ListNode* ;pre ;= ;helper;
18 ; ; ; ; ; ; ;ListNode* ;cur ;= ;head;
19 ; ; ; ; ; ; ;
20 ; ; ; ; ; ; ;while(cur ;!= ;NULL){
21 ; ; ; ; ; ; ; ; ; ; ;ListNode* ;next ;= ;cur->next;
22 ; ; ; ; ; ; ; ; ; ; ;//保存head位置
23 ; ; ; ; ; ; ; ; ; ; ;pre ;= ;helper;
24 ; ; ; ; ; ; ; ; ; ; ;while(pre->next ;!= ;NULL ;&& ;pre->next->val ;< ;cur->val){
25 ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;pre ;= ;pre->next;
26 ; ; ; ; ; ; ; ; ; ; ;}
27 ; ; ; ; ; ; ; ; ; ; ;//插入
28 ; ; ; ; ; ; ; ; ; ; ;cur->next ;= ;pre->next;
29 ; ; ; ; ; ; ; ; ; ; ;pre->next ;= ;cur;
30 ; ; ; ; ; ; ; ; ; ; ;//恢复
31 ; ; ; ; ; ; ; ; ; ; ;
32 ; ; ; ; ; ; ; ; ; ; ;cur ;= ;next;
33 ; ; ; ; ; ; ;}
34 ; ; ; ; ; ; ;return ;helper->next;
35 ; ; ; ; ;}
36 ;};</pre> ; ;