問題：用插入排序?qū)︽湵砼判?/p>

思路：使用鏈表中開頭的兩個(gè)node，建立一個(gè)新的鏈表。然后依次從舊的鏈表第三個(gè)node開始取值，進(jìn)行插入排序。

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. 在建立新的鏈表過程中，為了減少空間復(fù)雜度，我沒有新建node，而是將原node進(jìn)行修改。這就牽涉到了對(duì)象實(shí)例的引用。我們可以通過引用來修改對(duì)象實(shí)例的值，但是要知道一旦修改，這個(gè)node的其他引用也會(huì)被修改。所以我們要將跳到下一個(gè)node的行為提前運(yùn)行，不然一旦被修改，next指針就會(huì)失去原目標(biāo)。

2. 在一開始的時(shí)候，我本來準(zhǔn)備用通用的程序來表達(dá)所有的特殊情況，例如在新的鏈表頭插入node，在新的鏈表尾插入node。但是最后都不得不拿出來單獨(dú)處理，可能是我沒想到吧，如有望告知。

Java

個(gè)人感覺任何程序一旦變成java就會(huì)復(fù)雜，我寫了幾次都存在超出內(nèi)存的情況，最后再網(wǎng)路上看到別人寫的，比我的要簡單很多，而且邏輯清晰，于是我就當(dāng)了一次代碼的搬運(yùn)工。。。原碼在這里

/**
 * 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;  
        //未排序游動(dòng)指針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:臨時(shí)節(jié)點(diǎn)指針，h：已排序部分游動(dòng)指針  
  
        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;  
    }  
}  

對(duì)比這兩種思路，一個(gè)是一邊寫，一邊處理出現(xiàn)的例外；一個(gè)是在寫之前就考慮好會(huì)出現(xiàn)的例外并拿出來單獨(dú)處理。

我感覺兩種方法都有各自的利弊，如若兩者結(jié)合起來，即以第二種為主，第一種為輔，這樣可能會(huì)好很多。