LeetCode : Sort a linked list with insertion sort.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    
    public ListNode insert(ListNode head,ListNode x)
    {
        ListNode pp=null;
        if(head==null)return x;

        for(ListNode p=head;p!=null;p=p.next)
        {
            if(x.val<p.val)
            {
                if(pp!=null)
                {
                    pp.next=x;
                    x.next=p;
                    return head;
                }
                else
                {
                    x.next=head;
                    return x;
                }
            }
            pp=p;
        }
        pp.next=x;           // dont 
        x.next=null;
        return head;
    }
    
    public ListNode insertionSortList(ListNode head) {
        
        ListNode ph,qh,qq;
        
        if(head==null)return head;
        if(head.next==null)return head;

        ph=head;
        qh=head.next;
        head.next=null;

        while(qh!=null)
        {
            qq=qh.next;      // we must use qq to save qh.next
                             // in case qh will change their structure 
                             // after insert()
            ph=insert(ph,qh);
            qh=qq;
        }
        return ph;
        
    }
}