package sort;

import linkedList.ListNode;
import org.junit.Test;

/**
 * @Author: wei1
 * @Date: Create in 2018/12/3 13:52
 * @Description:
 */
public class InsertionSortList {
    public ListNode insertionSortList(ListNode head) {
        while (head == null || head.next == null) {
            return head;
        }
        ListNode p1 = head;
        ListNode newHead = new ListNode(Integer.MIN_VALUE);
        ListNode newHead1 = newHead;
        ListNode newHead2 = newHead.next;
        ListNode curi;
        for (ListNode i = head; i != null; ) {
            curi = i;
            i = i.next;
            ListNode curj = newHead;
            for (ListNode j = newHead;; ) {
                curj = j;
                j = j.next;
                if (j == null || curi.val <= j.val) {
                    break;
                }
            }
            curi.next = curj.next;
            curj.next = curi;
        }

        return newHead.next;
    }

    @Test
    public void test() {
        //        4->2->1->3
        ListNode l1 = new ListNode(4);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(1);
        l1.next.next.next = new ListNode(3);
        ListNode listNode = insertionSortList(l1);
        System.out.println(listNode);
    }
}