package com.fishercoder.solutions;

import com.fishercoder.common.classes.ListNode;

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

/**
 * 147. Insertion Sort List
 *
 * Sort a linked list using insertion sort.
 *
 * Algorithm of Insertion Sort:
 *
 *     Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
 *     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.
 *     It repeats until no input elements remain.
 *
 *
 * Example 1:
 *
 * Input: 4->2->1->3
 * Output: 1->2->3->4
 *
 * Example 2:
 *
 * Input: -1->5->3->4->0
 * Output: -1->0->3->4->5
 */
public class _147 {

  public static class Solution1 {
    public ListNode insertionSortList(ListNode head) {
      ListNode temp = head;
      List<Integer> list = new ArrayList<>();
      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,585 +134,8 @@
 t;%0A%0A
-/**%0A * 147. Insertion Sort List%0A *%0A * Sort a linked list using insertion sort.%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 */%0A
 publ
@@ -151,16 +151,18 @@
 _147 %7B%0A%0A
+  
   public
@@ -187,24 +187,28 @@
 tion1 %7B%0A    
+   
+ 
 public ListN
@@ -242,24 +242,30 @@
 ode head) %7B%0A
+      
       ListNo
@@ -282,24 +282,30 @@
 head;%0A      
+     
+ 
 List%3CInteger
@@ -332,16 +332,22 @@
 st%3C%3E();%0A
+      
       wh
@@ -375,16 +375,24 @@
         
+     
+   
 list.add
@@ -411,16 +411,24 @@
         
+   
+     
 temp = t
@@ -439,26 +439,38 @@
 next;%0A      
+ 
-%7D%0A
+     %7D%0A      
       Intege
@@ -520,16 +520,22 @@
 ze()%5D);%0A
+      
       fo
@@ -572,32 +572,40 @@
  i++) %7B%0A        
+       
+ 
 for (int j = i -
@@ -619,24 +619,34 @@
 = 0; j--) %7B%0A
+          
           if
@@ -668,24 +668,36 @@
 s%5Bj + 1%5D) %7B%0A
+            
             
@@ -719,16 +719,28 @@
 ums%5Bj%5D;%0A
+            
         
@@ -766,16 +766,28 @@
 j + 1%5D;%0A
+            
         
@@ -827,28 +827,58 @@
     
+          %7D%0A                
 %7D%0A     
-   %7D%0A
       
+ 
 %7D%0A
+      
     
@@ -906,24 +906,30 @@
 head;%0A      
+     
+ 
 for (int i =
@@ -948,32 +948,40 @@
 .length; i++) %7B%0A
+        
         newHead.
@@ -999,24 +999,32 @@
 i%5D;%0A        
+   
+     
 newHead = ne
@@ -1031,24 +1031,30 @@
 wHead.next;%0A
+      
       %7D%0A    
@@ -1055,16 +1055,22 @@
 %7D%0A      
+ 
+     
 return h
@@ -1078,16 +1078,22 @@
 ad;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 147