[Leetcode][JAVA] Insertion Sort List

浏览数：39 / 时间：2015年06月08日

Sort a linked list using insertion sort.

简单插入排序，先写个插入一个值到链表里的函数，再遍历整个链表，一个一个把值插入新链表中：

 1  public ListNode insertionSortList(ListNode head) {
 2         if(head==null)
 3             return null;
 4         ListNode re = new ListNode(head.val);
 5         ListNode cur = head.next;
 6         while(cur!=null)
 7         {
 8             re = insert(re, cur.val);
 9             cur = cur.next;
10         }
11         return re;
12     }
13     
14     public ListNode insert(ListNode head, int v)
15     {
16         ListNode ln = new ListNode(v);
17         ListNode cur = head;
18         ListNode helper = new ListNode(0);
19         helper.next = head;
20         ListNode pre = helper;
21         
22         while(cur!=null)
23         {
24             if(v<cur.val)
25             {
26                 pre.next = ln;
27                 ln.next = cur;
28                 return helper.next;
29             }
30             pre = cur;
31             cur = cur.next;
32         }
33         pre.next = ln;
34         ln.next = null;
35         return helper.next;
36     }

递归实现：

 1 public ListNode insertionSortList(ListNode head) {
 2         if(head==null || head.next==null)
 3             return head;
 4         int value = head.val;
 5         return insert(insertionSortList(head.next),value);
 6     }
 7     
 8     public ListNode insert(ListNode head, int v)
 9     {
10         ListNode ln = new ListNode(v);
11         ListNode cur = head;
12         ListNode helper = new ListNode(0);
13         helper.next = head;
14         ListNode pre = helper;
15         
16         while(cur!=null)
17         {
18             if(v<cur.val)
19             {
20                 pre.next = ln;
21                 ln.next = cur;
22                 return helper.next;
23             }
24             pre = cur;
25             cur = cur.next;
26         }
27         pre.next = ln;
28         ln.next = null;
29         return helper.next;
30     }