[leetcode]Insertion Sort List

Sort a linked list using insertion sort.

算法思路：

最基本的插入排序，时间复杂度O(n*n)，空间复杂度O(1)

代码：

 1 public class Solution {
 2     public ListNode insertionSortList(ListNode head) {
 3         if(head == null || head.next == null) return head;
 4         ListNode list = new ListNode(0);
 5         list.next = head;
 6         head = head.next;
 7         list.next.next = null;
 8         while(head != null){
 9             ListNode tail = list;
10             ListNode node = head;
11             head = head.next;
12             node.next = null;
13             while(tail != null){
14                 if(tail.next == null){
15                     tail.next = node;
16                     break;
17                 }
18                 if(tail.next.val > node.val){
19                     node.next = tail.next;
20                     tail.next = node;
21                     break;
22                 }else{
23                     tail = tail.next;
24                 }
25             }
26         }
27         return list.next;
28     }
29 }