package com.fishercoder.solutions;

import com.fishercoder.common.classes.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Sort a linked list using insertion sort.
 */
public class _147 {

    public ListNode insertionSortList(ListNode head) {
        ListNode temp = head;
        List<Integer> list = new ArrayList<Integer>();
        while (temp != null) {
            list.add(temp.val);
            temp = temp.next;
        }
        Integer[] nums = list.toArray(new Integer[list.size()]);
        for (int i = 1; i < list.size(); i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] > nums[j + 1]) {
                    int tempNum = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tempNum;
                }
            }
        }
        ListNode newHead = head;
        for (int i = 0; i < nums.length; i++) {
            newHead.val = nums[i];
            newHead = newHead.next;
        }
        return head;
    }

}

@@ -134,16 +134,47 @@
 t;%0A%0A/**%0A
+ * 147. Insertion Sort List%0A *%0A
  * Sort 
@@ -215,30 +215,558 @@
 .%0A *
-/%0Apublic class _147 %7B%0A
+%0A * Algorithm of Insertion Sort:%0A *%0A *     Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.%0A *     At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.%0A *     It repeats until no input elements remain.%0A *%0A *%0A * Example 1:%0A *%0A * Input: 4-%3E2-%3E1-%3E3%0A * Output: 1-%3E2-%3E3-%3E4%0A *%0A * Example 2:%0A *%0A * Input: -1-%3E5-%3E3-%3E4-%3E0%0A * Output: -1-%3E0-%3E3-%3E4-%3E5%0A */%0Apublic class _147 %7B%0A%0A  public static class Solution1 %7B
 %0A   
@@ -819,26 +819,24 @@
 ad) %7B%0A      
-  
 ListNode tem
@@ -847,26 +847,24 @@
 head;%0A      
- 
- 
 List%3CInteger
@@ -890,22 +890,13 @@
 ist%3C
-Integer
 %3E();%0A
-  
     
@@ -928,20 +928,16 @@
         
-    
 list.add
@@ -956,20 +956,16 @@
         
-  
-  
 temp = t
@@ -980,26 +980,24 @@
 ;%0A      
-  
 %7D%0A      
   Intege
@@ -988,18 +988,16 @@
 %7D%0A      
- 
- 
 Integer%5B
@@ -1043,34 +1043,32 @@
 size()%5D);%0A      
-  
 for (int i = 1; 
@@ -1095,28 +1095,24 @@
 ) %7B%0A        
-  
-  
 for (int j =
@@ -1144,22 +1144,16 @@
         
-      
 if (nums
@@ -1185,24 +1185,16 @@
         
-  
-      
 int temp
@@ -1216,32 +1216,24 @@
             
-    
-    
 nums%5Bj%5D = nu
@@ -1243,24 +1243,16 @@
 j + 1%5D;%0A
-        
         
@@ -1292,26 +1292,18 @@
     
-      %7D%0A  
+%7D%0A
         
   %7D%0A
@@ -1294,30 +1294,26 @@
   %7D%0A        
-  %7D%0A  
+%7D%0A
       %7D%0A    
@@ -1310,26 +1310,24 @@
     %7D%0A      
- 
- 
 ListNode new
@@ -1335,26 +1335,24 @@
 ead = head;%0A
-  
       for (i
@@ -1389,28 +1389,24 @@
 ) %7B%0A        
-  
-  
 newHead.val 
@@ -1416,20 +1416,16 @@
 ums%5Bi%5D;%0A
-    
         
@@ -1450,30 +1450,26 @@
 next;%0A      
-  %7D%0A  
+%7D%0A
       return
@@ -1481,11 +1481,14 @@
 ;%0A    %7D%0A
+  %7D
 %0A%7D%0A

refactor 147