题目：
Sort a linked list using insertion sort.
思路：
插入排序是一种O(n^2)复杂度的算法，基本想法相信大家都比较了解，就是每次循环找到一个元素在当前排好的结果中相对应的位置，然后插进去，经过n次迭代之后就得到排好序的结果了。了解了思路之后就是链表的基本操作了，搜索并进行相应的插入。时间复杂度是排序算法的O(n^2)，空间复杂度是O(1)。
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var insertionSortList = function(head) { if(head==null||head.next==null){ return head; } var tempHead=new ListNode(0),p=head,tp=null; while(p!=null){ tp=tempHead; while(tp.next!=null&&tp.next.val<p.val){ tp=tp.next; } var tempNode1=tp.next; var tempNode2=p.next; tp.next=p; p.next=tempNode1; p=tempNode2; } return tempHead.next; };
原文：http://www.cnblogs.com/shytong/p/5146813.html