Insertion-Sort-List.cs

namespace_147_Insertion_Sort_List
{
publicclassSolution
{
publicListNodeInsertionSortList(ListNodehead)
{
ListNodedummy=newListNode(0);
ListNodeprev=dummy;
while(head!=null)
{
ListNodetemp=head.next;

/* Before insert, the prev is at the last node of the sorted list.
 Only the last node's value is larger than the current inserting node 
 should we move the temp back to the head*/
if(prev.val>=head.val)prev=dummy;

while(prev.next!=null&&prev.next.val<head.val)
{
prev=prev.next;
}

head.next=prev.next;
prev.next=head;
// prev = dummy; // Don't set prev to the head of the list after insert
head=temp;
}
returndummy.next;
}
}
publicclassListNode
{
publicintval;
publicListNodenext;
publicListNode(intval=0,ListNodenext=null)
{
this.val=val;
this.next=next;
}
}
}