問題：用插入排序?qū)︽湵砼判?/p>
思路：使用鏈表中開頭的兩個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
思考：
在建立新的鏈表過程中征冷，為了減少空間復(fù)雜度，我沒有新建node誓琼，而是將原node進行修改检激。這就牽涉到了對象實例的引用。我們可以通過引用來修改對象實例的值腹侣，但是要知道一旦修改叔收，這個node的其他引用也會被修改。所以我們要將跳到下一個node的行為提前運行傲隶，不然一旦被修改饺律，next指針就會失去原目標(biāo)。
在一開始的時候伦籍，我本來準(zhǔn)備用通用的程序來表達所有的特殊情況蓝晒，例如在新的鏈表頭插入node腮出，在新的鏈表尾插入node。但是最后都不得不拿出來單獨處理芝薇，可能是我沒想到吧胚嘲，如有望告知。
Java
個人感覺任何程序一旦變成java就會復(fù)雜洛二，我寫了幾次都存在超出內(nèi)存的情況馋劈，最后再網(wǎng)路上看到別人寫的，比我的要簡單很多晾嘶，而且邏輯清晰妓雾，于是我就當(dāng)了一次代碼的搬運工。垒迂。械姻。原碼在這里
/**
* 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:臨時節(jié)點指針，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;
}
}
對比這兩種思路机断，一個是一邊寫楷拳，一邊處理出現(xiàn)的例外；一個是在寫之前就考慮好會出現(xiàn)的例外并拿出來單獨處理吏奸。
我感覺兩種方法都有各自的利弊欢揖，如若兩者結(jié)合起來，即以第二種為主奋蔚，第一種為輔她混，這樣可能會好很多。
