思路

1. 插入排序的思想，将未排序的与已知排好序的作比较，进行插入
2. 创建一个链表来作为已知链表(rptr)， 比较的是每一个节点的next节点的val值，进行插入
3. 遍历原链表时，需要记录下位置已经比较的位置

代码

package linkList;

/**
 * Sort a linked list using insertion sort.
 * Created by liqiushi on 2018/1/10.
 */
public class InsertionSortList {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode rptr = new ListNode(0);
       
        while (head != null) {
            ListNode qptr = rptr;
            ListNode pptr = head;
            head = head.next;
            while (qptr.next != null && qptr.next.val < pptr.val)
                qptr = qptr.next;
            pptr.next = qptr.next;
            qptr.next = pptr;
        }
        return rptr.next;
    }
}