LeetCode 147 - Insertion Sort List

https://leetcode.com/problems/insertion-sort-list

Sort a linked list using insertion sort.

https://discuss.leetcode.com/topic/8570/an-easy-and-clear-way-to-sort-o-1-space

public ListNode insertionSortList(ListNode head) {
  if( head == null ){
   return head;
  }
  
  ListNode helper = new ListNode(0); //new starter of the sorted list
  ListNode cur = head; //the node will be inserted
  ListNode pre = helper; //insert node between pre and pre.next
  ListNode next = null; //the next node will be inserted
  //not the end of input list
  while( cur != null ){
   next = cur.next;
   //find the right place to insert
   while( pre.next != null && pre.next.val < cur.val ){
    pre = pre.next;
   }
   //insert between pre and pre.next
   cur.next = pre.next;
   pre.next = cur;
   pre = helper;
   cur = next;
  }
  
  return helper.next;
 }

https://discuss.leetcode.com/topic/1855/accepted-solution-using-java
https://discuss.leetcode.com/topic/18097/clean-java-solution-using-a-fake-head
http://www.jiuzhang.com/solutions/insertion-sort-list/

public ListNode insertionSortList(ListNode head) {
  ListNode curr = head, next = null;
  // l is a fake head
  ListNode l = new ListNode(0);
  
  while (curr != null) {
    next = curr.next;
    
    ListNode p = l;
    while (p.next != null && p.next.val < curr.val)
      p = p.next;
    
    // insert curr between p and p.next
    curr.next = p.next;
    p.next = curr;
    curr = next;
  }
  
  return l.next;
}

Insertion Sort for Singly Linked List - GeeksQuiz
http://www.geeksforgeeks.org/recursive-insertion-sort/

void insertionSortRecursive(int arr[], int n)

{

    // Base case

    if (n <= 1)

        return;

 

    // Sort first n-1 elements

    insertionSortRecursive( arr, n-1 );

 

    // Insert last element at its correct position

    // in sorted array.

    int last = arr[n-1];

    int j = n-2;

 

    /* Move elements of arr[0..i-1], that are

      greater than key, to one position ahead

      of their current position */

    while (j >= 0 && arr[j] > last)

    {

        arr[j+1] = arr[j];

        j--;

    }

    arr[j+1] = last;

}