问题：用插入排序对链表排序

思路：使用链表中开头的两个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

思考：

1. 在建立新的链表过程中，为了减少空间复杂度，我没有新建node，而是将原node进行修改。这就牵涉到了对象实例的引用。我们可以通过引用来修改对象实例的值，但是要知道一旦修改，这个node的其他引用也会被修改。所以我们要将跳到下一个node的行为提前运行，不然一旦被修改，next指针就会失去原目标。

2. 在一开始的时候，我本来准备用通用的程序来表达所有的特殊情况，例如在新的链表头插入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;  
    }  
}  

对比这两种思路，一个是一边写，一边处理出现的例外；一个是在写之前就考虑好会出现的例外并拿出来单独处理。

我感觉两种方法都有各自的利弊，如若两者结合起来，即以第二种为主，第一种为辅，这样可能会好很多。