package cn.edu.algorithm.huawei;

public class Solution {

    public ListNode insertionSortList(ListNode head) {

        //哑节点

        ListNode dumy = new ListNode(Integer.MIN_VALUE);

        ListNode cur = head;

        ListNode pre = dumy;

        while (cur != null) {

            //保存当前节点下一个节点

            ListNode next = cur.next;

            pre = dumy;

            //寻找当前节点正确位置的一个节点

            while (pre.next != null && pre.next.val < cur.val) {

                pre = pre.next;

            }

            //将当前节点加入新链表中

            cur.next = pre.next;//指向插入位置后面的节点

            ListNode test = cur.next;

            pre.next = cur;

            //处理下一个节点

            cur = next;

        }

        return dumy.next;

    }

    public static void main(String[] args) {

        ListNode head = new ListNode(2);

        head.next = new ListNode(1);

        Solution solution = new Solution();

        ListNode list = solution.insertionSortList(head);

        while (list != null) {

            System.out.println(list.val);

            list = list.next;

        }

    }

}

class ListNode {

    int val;

    ListNode next;

    ListNode(int x) {

        val = x;

        next = null;

    }

    @Override

    public String toString() {

        return val + "";

    }

}