[LeetCode] Insertion Sort List

Insertion Sort List
Sort a linked list using insertion sort.
Solution: The power of recursion. We first sort the remaining list, and then we insert the head node. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode insertionSortList(ListNode head) { if (head == null || head.next == null) return head; ListNode h = insertionSortList(head.next); head.next = null; if (head.val < h.val) { head.next = h; return head; } ListNode pre = h; ListNode cur = h.next; while (cur != null && cur.val < head.val) { pre = cur; cur = cur.next; } pre.next = head; head.next = cur; return h; } }