Insertion Sort List

Problem

Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list's head.

The steps of the insertion sort algorithm:

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.

The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.

Example

Given 1->3->2->0->null, return 0->1->2->3->null.

Solution

Essentially we are creating a new linked list and keep it sorted, and adding the nodes in the input linked list to the sorted linked list one-by-one.

• Create a Node sortedHead as the head of the sorted list.
• For each input node:
  • Start from the sortedHead, create a new pointer p, since this list is sorted, move p forward until if finds the correct position for head of the remaining input list.
  • Insert the head of the remaining list in the sorted list (hence the name "insertion sort")
• After all the nodes are inserted, return sortedHead.next (since sortedHead is a dummy node that has no values).