Insertion Sort List · 數據結構與算法/leetcode/lintcode題解

# Insertion Sort List ### Source - leetcode: [Insertion Sort List | LeetCode OJ](https://leetcode.com/problems/insertion-sort-list/) - lintcode: [(173) Insertion Sort List](http://www.lintcode.com/en/problem/insertion-sort-list/) ~~~ Sort a linked list using insertion sort. Example Given 1->3->2->0->null, return 0->1->2->3->null. ~~~ ### 題解1 - 從首到尾遍歷插入排序常見的實現是針對數組的，如前幾章總的的 [Insertion Sort](http://algorithm.yuanbin.me/zh-cn/basics_sorting/insertion_sort.html)，但這道題中的排序的數據結構為單向鏈表，故無法再從后往前遍歷比較值的大小了。好在天無絕人之路，我們還可以**從前往后依次遍歷比較和交換。** 由于排序后頭節點不一定，故需要引入 dummy 大法，并以此節點的`next`作為最后返回結果的頭節點，返回的鏈表從`dummy->next`這里開始構建。首先我們每次都從`dummy->next`開始遍歷，依次和上一輪處理到的節點的值進行比較，直至找到不小于上一輪節點值的節點為止，隨后將上一輪節點插入到當前遍歷的節點之前，依此類推。文字描述起來可能比較模糊，大家可以結合以下的代碼在紙上分析下。 ### Python ~~~ """ 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): dummy = ListNode(0) cur = head while cur is not None: pre = dummy while pre.next is not None and pre.next.val < cur.val: pre = pre.next temp = cur.next cur.next = pre.next pre.next = cur cur = temp return dummy.next ~~~ ### C++ ~~~ /** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @return: The head of linked list. */ ListNode *insertionSortList(ListNode *head) { ListNode *dummy = new ListNode(0); ListNode *cur = head; while (cur != NULL) { ListNode *pre = dummy; while (pre->next != NULL && pre->next->val < cur->val) { pre = pre->next; } ListNode *temp = cur->next; cur->next = pre->next; pre->next = cur; cur = temp; } return dummy->next; } }; ~~~ ### Java ~~~ /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode insertionSortList(ListNode head) { ListNode dummy = new ListNode(0); ListNode cur = head; while (cur != null) { ListNode pre = dummy; while (pre.next != null && pre.next.val < cur.val) { pre = pre.next; } ListNode temp = cur.next; cur.next = pre.next; pre.next = cur; cur = temp; } return dummy.next; } } ~~~ ### 源碼分析 1. 新建 dummy 節點，用以處理最終返回結果中頭節點不定的情況。 1. 以`cur`表示當前正在處理的節點，在從 dummy 開始遍歷前保存`cur`的下一個節點作為下一輪的`cur`. 1. 以`pre`作為遍歷節點，直到找到不小于`cur`值的節點為止。 1. 將`pre`的下一個節點`pre->next`鏈接到`cur->next`上，`cur`鏈接到`pre->next`, 最后將`cur`指向下一個節點。 1. 返回`dummy->next`最為最終頭節點。 Python 的實現在 lintcode 上會提示 [TLE](# "Time Limit Exceeded 的簡稱。你的程序在 OJ 上的運行時間太長了，超過了對應題目的時間限制。"), leetcode 上勉強通過，這里需要注意的是采用`if A is not None:`的效率要比`if A:`高，不然 leetcode 上也過不了。具體原因可參考 [Stack Overflow](http://stackoverflow.com/questions/7816363/if-a-vs-if-a-is-not-none) 上的討論。 ### 復雜度分析最好情況：原鏈表已經有序，每得到一個新節點都需要 iii 次比較和一次交換, 時間復雜度為 1/2O(n2)+O(n)1/2O(n^2) + O(n)1/2O(n2)+O(n), 使用了 dummy 和 pre, 空間復雜度近似為 O(1)O(1)O(1). 最壞情況：原鏈表正好逆序，由于是單向鏈表只能從前往后依次遍歷，交換和比較次數均為 1/2O(n2)1/2 O(n^2)1/2O(n2), 總的時間復雜度近似為 O(n2)O(n^2)O(n2), 空間復雜度同上，近似為 O(1)O(1)O(1). ### 題解2 - 優化有序鏈表從題解1的復雜度分析可以看出其在最好情況下時間復雜度都為 O(n2)O(n^2)O(n2) ，這顯然是需要優化的。仔細觀察可發現最好情況下的比較次數是可以優化到 O(n)O(n)O(n) 的。思路自然就是先判斷鏈表是否有序，僅對降序的部分進行處理。優化之后的代碼就沒題解1那么容易寫對了，建議畫個圖自行紙上分析下。 ### Python ~~~ """ 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): dummy = ListNode(0) dummy.next = head cur = head while cur is not None: if cur.next is not None and cur.next.val < cur.val: # find insert position for smaller(cur->next) pre = dummy while pre.next is not None and pre.next.val < cur.next.val: pre = pre.next # insert cur->next after pre temp = pre.next pre.next = cur.next cur.next = cur.next.next pre.next.next = temp else: cur = cur.next return dummy.next ~~~ ### C++ ~~~ /** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @return: The head of linked list. */ ListNode *insertionSortList(ListNode *head) { ListNode *dummy = new ListNode(0); dummy->next = head; ListNode *cur = head; while (cur != NULL) { if (cur->next != NULL && cur->next->val < cur->val) { ListNode *pre = dummy; // find insert position for smaller(cur->next) while (pre->next != NULL && pre->next->val <= cur->next->val) { pre = pre->next; } // insert cur->next after pre ListNode *temp = pre->next; pre->next = cur->next; cur->next = cur->next->next; pre->next->next = temp; } else { cur = cur->next; } } return dummy->next; } }; ~~~ ### Java ~~~ /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode insertionSortList(ListNode head) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode cur = head; while (cur != null) { if (cur.next != null && cur.next.val < cur.val) { // find insert position for smaller(cur->next) ListNode pre = dummy; while (pre.next != null && pre.next.val < cur.next.val) { pre = pre.next; } // insert cur->next after pre ListNode temp = pre.next; pre.next = cur.next; cur.next = cur.next.next; pre.next.next = temp; } else { cur = cur.next; } } return dummy.next; } } ~~~ ### 源碼分析 1. 新建 dummy 節點并將其`next` 指向`head` 1. 分情況討論，僅需要處理逆序部分。 1. 由于已經確認鏈表逆序，故僅需將較小值(`cur->next`而不是`cur`)的節點插入到鏈表的合適位置。 1. 將`cur->next`插入到`pre`之后，這里需要四個步驟，需要特別小心！ ![Insertion Sort](https://box.kancloud.cn/2015-10-24_562b1f502445b.png) 如上圖所示，將`cur->next`插入到`pre`節點后大致分為3個步驟。 ### 復雜度分析最好情況下時間復雜度降至 O(n)O(n)O(n), 其他同題解1. ### Reference - [Explained C++ solution (24ms) - Leetcode Discuss](https://leetcode.com/discuss/37574/explained-c-solution-24ms) - [Insertion Sort List - 九章算法](http://www.jiuzhang.com/solutions/insertion-sort-list/)