题目：
Sort a linked list using insertion sort.
分析：
使用插入排序法对一个链表进行排序。
没有什么特别深奥之处。注意处理好边界情况即可。
代码：
Java
|
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 |
public class Solution { public ListNode insertionSortList(ListNode head) { if(head == null) return head; ListNode fakeHead = new ListNode(1 << 31); fakeHead.next = head; ListNode tail = head; while(tail.next != null){ // If the current checked node is the largest one, don't move it. // Go check next. if(tail.next.val >= tail.val) tail = tail.next; else{ ListNode p = fakeHead; while(true){ if(p.next != null && p.next.val > tail.next.val){ ListNode next = p.next; p.next = tail.next; tail.next = tail.next.next; p.next.next = next; break; } p = p.next; } } } return fakeHead.next; } } |