Sort a linked list using insertion sort.
public class Solution { public ListNode insertionSortList(ListNode head) { if(head == null || head.next == null) return head; ListNode p2 = head; ListNode fake = new ListNode(-2147483648); ListNode p1 = fake; while(p2 != null){ ListNode pre = insert(p1,p2); ListNode originalNext = p2.next; //find insert place p2.next = pre.next; pre.next = p2; p2 = originalNext; } return fake.next; } public ListNode insert(ListNode p1, ListNode p2){ ListNode pre = null; ListNode cur = p1;//when meet move mutiple position, add variable for node while(cur!=null &&cur.val <= p2.val){ pre = cur; cur = cur.next; } return pre; } }
public class Solution { public ListNode insertionSortList(ListNode head) { if(head == null || head.next == null) return head; ListNode preHead = new ListNode(-99); preHead.next = head; ListNode run = head; while(run != null && run.next!=null){ if(run.val > run.next.val){ ListNode small = run.next; ListNode pre = preHead; while(pre.next.val < small.val){ pre = pre.next; } ListNode temp = pre.next; pre.next = small; run.next = small.next; small.next = temp;// here } else{ run = run.next; } } return preHead.next; } }
mistakes: small has to connect to temp
learned: connect from beginning to smaller to run // prev -> run -> small ----> prev - small -> run