package com.leetcode.problem;

/**
 * @author pxu
 * @create 2020-04-22 21:51
 */
public class Problem147 {

    public static void main(String[] args) {

        ListNode n4 = new ListNode(3);
        ListNode n3 = new ListNode(1);
        n3.next = n4;
        ListNode n2 = new ListNode(2);
        n2.next = n3;
        ListNode n1 = new ListNode(4);
        n1.next = n2;

        ListNode res = insertionSortList(n1);
        while(res!=null)
        {
            System.out.println(res.val);
            res = res.next;
        }

    }


    public static ListNode insertionSortList(ListNode head) {

        if(head == null || head.next == null)
            return head;

        ListNode pre = head;
        ListNode cur = head.next;

        while(cur!=null)
        {
            if(cur.val<pre.val)
            {
                ListNode p = null;
                ListNode q = head;

                while(q.val<=cur.val && q!=cur)
                {
                    p = q;
                    q = q.next;
                }

                pre.next = cur.next;

                if(p == null)
                {
                    cur.next = head;
                    head = cur;
                }
                else
                {
                    cur.next = p.next;
                    p.next = cur;
                }

                cur = pre.next;
            }
            else
            {
                pre = cur;
                cur = cur.next;
            }

        }

        return head;

    }


}

class ListNode
{
    int val;
    ListNode next;
    ListNode(int x) { val = x; }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}

04-23 04:35