问题：用插入排序对链表排序
思路：使用链表中开头的两个node，建立一个新的链表。然后依次从旧的链表第三个node开始取值，进行插入排序。
Python3
"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param head: The first node of linked list.
@return: The head of linked list.
"""
def insertionSortList(self, head):
if head == None and head.next == None:
return head
# a flexible point of ranked list
ranked_point = head
# a flexible point of raw list
raw_point = head.next
point = raw_point
# seperate the list into 2 lists
head.next = None
while raw_point != None:
while ranked_point != None:
# if new node is smaller than current node
if raw_point.val <= ranked_point.val:
# jump to next node of the raw list
raw_point = raw_point.next
# insert this new node into the list
point.next = ranked_point
# if the new node is smallest one
if ranked_point == head:
# refresh the head
head = point
point = raw_point
break
# if the new node is the largest one in ranked list
if ranked_point.next == None:
# insert it into the tail of the ranked list
ranked_point.next = raw_point
# jump to next node of the raw list
raw_point = raw_point.next
ranked_point.next.next = None
break
ranked_point = ranked_point.next
ranked_point = head
return head
思考：
在建立新的链表过程中，为了减少空间复杂度，我没有新建node，而是将原node进行修改。这就牵涉到了对象实例的引用。我们可以通过引用来修改对象实例的值，但是要知道一旦修改，这个node的其他引用也会被修改。所以我们要将跳到下一个node的行为提前运行，不然一旦被修改，next指针就会失去原目标。
在一开始的时候，我本来准备用通用的程序来表达所有的特殊情况，例如在新的链表头插入node，在新的链表尾插入node。但是最后都不得不拿出来单独处理，可能是我没想到吧，如有望告知。
Java
个人感觉任何程序一旦变成java就会复杂，我写了几次都存在超出内存的情况，最后再网路上看到别人写的，比我的要简单很多，而且逻辑清晰，于是我就当了一次代码的搬运工。。。原码在这里
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param head: The first node of linked list.
* @return: The head of linked list.
*/
public ListNode insertionSortList(ListNode head) {
// incase that the list is null or only one element
if (head == null || head.next == null)
return head;
//未排序游动指针C
ListNode c = head.next;
// break the list into 2 list, one is ranked list; another one is the raw list.
head.next = null;
ListNode pt, h; //pt:临时节点指针，h：已排序部分游动指针
while (c != null) {
// jump to the next node
pt = c;
c = c.next;
// make the new node link to null
pt.next = null;
// point h to the head
h = head;
if (head.val > pt.val) { //比较头部
pt.next = head;
head = pt;
continue;
}
while (h.next != null) { //比较有序部分
if (h.next.val > pt.val) {
pt.next = h.next;
h.next = pt;
break;
}
// jump to the next node
h = h.next;
}
if (h.next == null) { //追加末尾
h.next = pt;
}
}
return head;
}
}
对比这两种思路，一个是一边写，一边处理出现的例外；一个是在写之前就考虑好会出现的例外并拿出来单独处理。
我感觉两种方法都有各自的利弊，如若两者结合起来，即以第二种为主，第一种为辅，这样可能会好很多。
