Insertion Sort List (LeetCode Linked List)

Question: Sort a linked list using insertion sort.

Idea: Create a constant dummy head. Then traversal the linked list. Whenever a node, say node i, is visited, initial a pointer to start from the dummy head and find the position to insert the node i.  After finishing the traversal, the sort is done. Return the dummy head's next node.

Time: O(n^2)  Space: O(1)

Code:

 public class Solution {  
   public ListNode insertionSortList(ListNode head) {  
     ListNode dummy=new ListNode(Integer.MIN_VALUE);  
     while(head!=null)  
     {  
       ListNode tmp=dummy;  
       while(tmp.next!=null&&tmp.next.val<head.val)  
         tmp=tmp.next;  
       ListNode nextNode=head.next;  
       head.next=tmp.next;  
       tmp.next=head;  
       head=nextNode;  
     }  
     return dummy.next;  
   }  
 }