Insertion Sort List

Sort a linked list using insertion sort.

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) {
 7  *         val = x;
 8  *         next = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     public ListNode insertionSortList(ListNode head) {
14         // IMPORTANT: Please reset any member data you declared, as
15         // the same Solution instance will be reused for each test case.
16         ListNode header = new ListNode(-1);
17         header.next = null;
18         if(head == null) return header.next;
19         ListNode cur = head;
20         while(cur != null){
21             ListNode tmp = header.next;
22             ListNode before = header;
23             while(tmp != null && tmp.val < cur.val){
24                 before = before.next;
25                 tmp = tmp.next;
26             }
27             before.next = cur;
28             ListNode a = cur.next;
29             cur.next = tmp;
30             cur = a;
31         }
32         return header.next;
33     }
34 }

第二遍：

 1 public class Solution {
 2     public ListNode insertionSortList(ListNode head) {
 3         // IMPORTANT: Please reset any member data you declared, as
 4         // the same Solution instance will be reused for each test case.
 5         if(head == null) return head;
 6         ListNode header = new ListNode(-1);
 7         ListNode cur = head, newbefore = header;
 8         while(cur != null){
 9             newbefore = header;
10             while(newbefore.next != null && newbefore.next.val < cur.val){
11                 newbefore = newbefore.next;
12             }
13             ListNode newcur = newbefore.next;
14             newbefore.next = cur;
15             ListNode tmp = cur.next;
16             cur.next = newcur;
17             cur = tmp;
18         }
19         return header.next;
20     }
21 }