久久精品中文字幕av,av.涩涩涩涩涩涩涩涩,亚洲国产日韩欧美精品成人久久久,成人福利电影免费在线观看,日产国产原创av,日韩av午夜激情,bt天堂中文字幕,超级碰人妻在线视频,欧美老熟妇久久一区二区

# 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 - 從首到尾遍歷 插入排序常見的實(shí)現(xiàn)是針對(duì)數(shù)組的，如前幾章總的的 [Insertion Sort](http://algorithm.yuanbin.me/zh-cn/basics_sorting/insertion_sort.html)，但這道題中的排序的數(shù)據(jù)結(jié)構(gòu)為單向鏈表，故無法再從后往前遍歷比較值的大小了。好在天無絕人之路，我們還可以**從前往后依次遍歷比較和交換。** 由于排序后頭節(jié)點(diǎn)不一定，故需要引入 dummy 大法，并以此節(jié)點(diǎn)的`next`作為最后返回結(jié)果的頭節(jié)點(diǎn)，返回的鏈表從`dummy->next`這里開始構(gòu)建。首先我們每次都從`dummy->next`開始遍歷，依次和上一輪處理到的節(jié)點(diǎn)的值進(jìn)行比較，直至找到不小于上一輪節(jié)點(diǎn)值的節(jié)點(diǎn)為止，隨后將上一輪節(jié)點(diǎn)插入到當(dāng)前遍歷的節(jié)點(diǎn)之前，依此類推。文字描述起來可能比較模糊，大家可以結(jié)合以下的代碼在紙上分析下。 ### 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 節(jié)點(diǎn)，用以處理最終返回結(jié)果中頭節(jié)點(diǎn)不定的情況。 1. 以`cur`表示當(dāng)前正在處理的節(jié)點(diǎn)，在從 dummy 開始遍歷前保存`cur`的下一個(gè)節(jié)點(diǎn)作為下一輪的`cur`. 1. 以`pre`作為遍歷節(jié)點(diǎn)，直到找到不小于`cur`值的節(jié)點(diǎn)為止。 1. 將`pre`的下一個(gè)節(jié)點(diǎn)`pre->next`鏈接到`cur->next`上，`cur`鏈接到`pre->next`, 最后將`cur`指向下一個(gè)節(jié)點(diǎn)。 1. 返回`dummy->next`最為最終頭節(jié)點(diǎn)。 Python 的實(shí)現(xiàn)在 lintcode 上會(huì)提示 [TLE](# "Time Limit Exceeded 的簡(jiǎn)稱。你的程序在 OJ 上的運(yùn)行時(shí)間太長了，超過了對(duì)應(yīng)題目的時(shí)間限制。"), leetcode 上勉強(qiáng)通過，這里需要注意的是采用`if A is not None:`的效率要比`if A:`高，不然 leetcode 上也過不了。具體原因可參考 [Stack Overflow](http://stackoverflow.com/questions/7816363/if-a-vs-if-a-is-not-none) 上的討論。 ### 復(fù)雜度分析 最好情況：原鏈表已經(jīng)有序，每得到一個(gè)新節(jié)點(diǎn)都需要 iii 次比較和一次交換, 時(shí)間復(fù)雜度為 1/2O(n2)+O(n)1/2O(n^2) + O(n)1/2O(n2)+O(n), 使用了 dummy 和 pre, 空間復(fù)雜度近似為 O(1)O(1)O(1). 最壞情況：原鏈表正好逆序，由于是單向鏈表只能從前往后依次遍歷，交換和比較次數(shù)均為 1/2O(n2)1/2 O(n^2)1/2O(n2), 總的時(shí)間復(fù)雜度近似為 O(n2)O(n^2)O(n2), 空間復(fù)雜度同上，近似為 O(1)O(1)O(1). ### 題解2 - 優(yōu)化有序鏈表 從題解1的復(fù)雜度分析可以看出其在最好情況下時(shí)間復(fù)雜度都為 O(n2)O(n^2)O(n2) ，這顯然是需要優(yōu)化的。 仔細(xì)觀察可發(fā)現(xiàn)最好情況下的比較次數(shù) 是可以優(yōu)化到 O(n)O(n)O(n) 的。思路自然就是先判斷鏈表是否有序，僅對(duì)降序的部分進(jìn)行處理。優(yōu)化之后的代碼就沒題解1那么容易寫對(duì)了，建議畫個(gè)圖自行紙上分析下。 ### 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 節(jié)點(diǎn)并將其`next` 指向`head` 1. 分情況討論，僅需要處理逆序部分。 1. 由于已經(jīng)確認(rèn)鏈表逆序，故僅需將較小值(`cur->next`而不是`cur`)的節(jié)點(diǎn)插入到鏈表的合適位置。 1. 將`cur->next`插入到`pre`之后，這里需要四個(gè)步驟，需要特別小心！  如上圖所示，將`cur->next`插入到`pre`節(jié)點(diǎn)后大致分為3個(gè)步驟。 ### 復(fù)雜度分析 最好情況下時(shí)間復(fù)雜度降至 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/)