Insertion Sort List

Sort a linked list using insertion sort.
Solution:
1. /*
2. * Definition for singly-linked list.
3. * public class ListNode {
4. * int val;
5. * ListNode next;
6. * ListNode(int x) { val = x; }
7. * }
8. /
9. public class Solution {
10. public ListNode insertionSortList(ListNode head) {
11. ListNode curr = head, next = null;
12. ListNode l = new ListNode(0);
13. 14. while (curr != null) {
15. next = curr.next;
16. 17. ListNode p = l;
18. while (p.next != null && p.next.val < curr.val) {
19. p = p.next;
20. }
21. 22. curr.next = p.next;
23. p.next = curr;
24. curr = next;
25. }
26. 27. return l.next;
28. }
29. }