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 +
'}';
}
}