leetcode 147.
Sort a linked list using insertion sort.
Solution. Create a dummyHead. Move the element in head into dummyHead list one by one. The process is like this:
public static ListNode insertionSortList(ListNode head) {
if (head == null) {
return head;
}
ListNode dummyHead = new ListNode(0);
while (head != null) {
// take out head to curr. head move to next
ListNode curr = head;
head = head.next;
// put curr to target position in dummyHead. Put curr between target and target.next
ListNode target = dummyHead;
while (target.next != null && target.next.val < curr.val) {
target = target.next;
}
curr.next = target.next;
target.next = curr;
}
return dummyHead.next;
}
Check my code on github.