public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode pre, next, record;
        ListNode p1;

        p1 = head.getNext();
        //if head.next is not set null, there will be a self-loop
        //test with case {1,1}
        head.setNext(null);

        while (p1 != null) {
            record = p1.getNext();
            if (p1.getVal() <= head.getVal()) {
                p1.setNext(head);
                head = p1;
            } else {
                pre = head;
                next = head.getNext();
                while (next != null && next.getVal() <= p1.getVal()) {
                    pre = next;
                    next = next.getNext();
                }
                p1.setNext(next);
                pre.setNext(p1);
            }
            p1 = record;
        }
        return head;
    }