摘要:插入排序維基百科一般來說,插入排序都采用在數組上實現。在放這個數之前,這個數的目標位置和原始位置之間的數都要先進行后移。最后,當,即遍歷完整個原鏈表之后,新鏈表排序完成。
Problem
Sort a linked list using insertion sort.
ExampleGiven 1->3->2->0->null, return 0->1->2->3->null.
Note插入排序【維基百科】
一般來說,插入排序都采用in-place在數組上實現。具體算法描述如下:
從第一個元素開始,該元素可以認為已經被排序
取出下一個元素,在已經排序的元素序列中從后向前掃描
如果該元素(已排序)大于新元素,將該元素移到下一位置
重復步驟3,直到找到已排序的元素小于或者等于新元素的位置
將新元素插入到該位置后
重復步驟2~5
關于插入排序,我所知道的就是從頭部開始,將每個數放到合適的位置。在放這個數之前,這個數的目標位置和原始位置之間的數都要先進行后移。然而這是一個in-place的操作,而對于鏈表而言,我們只要做一個空鏈表,然后不斷加入原鏈表中的最小元素即可。
cur是原鏈表head的指針,不斷向后掃描;node是空鏈表dummy的指針,用node.next與cur所指向的結點進行比較,一旦發現排列好的新鏈表中有大于cur的結點,就把cur放在node.next,然后進行下一輪循環:cur.next作為原鏈表新的cur,node返回新鏈表起點dummy。最后,當cur = null,即遍歷完整個原鏈表之后,新鏈表排序完成。返回dummy.next即可。
</>復制代碼
public class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummy = new ListNode(0);
ListNode cur = head;
while (cur != null) {
ListNode node = dummy;
while (node.next != null && node.next.val < cur.val) node = node.next;
ListNode temp = cur.next;
cur.next = node.next;
node.next = cur;
cur = temp;
}
return dummy.next;
}
}
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/65665.html
摘要:可以不要用太簡單的方法。先把它裝滿,再和隊列頂端的數字比較,大的就替換掉,小的就。遍歷完所有元素之后,頂部的數就是第大的數。 Problem Find K-th largest element in an array. Example In array [9,3,2,4,8], the 3rd largest element is 4.In array [1,2,3,4,5], the...
摘要:解題思路題目很簡單,就是要求用插入排序的方法來為鏈表排序。插入排序就是每次遍歷一個新的元素,將其插入到前面已經排好序的元素中。但要注意我們要將的前一個節點記錄下來在找到中點后,我們要將這樣鏈表才能分割成個。 Insertion Sort ListSort a linked list using insertion sort. 1.解題思路 題目很簡單,就是要求用插入排序的方法來為鏈表排...
注意新的list跟原來的list是不相連的,然后把各個狀態的點記錄好就行: public ListNode insertionSortList(ListNode head) { if (head == null || head.next == null) return head; //We started a new list here, not ...
摘要:這道題目可以用分治法來做,首先從鏈表中點分割鏈表,然后將兩個鏈表重新排序并合并。 Problem Sort a linked list in O(n log n) time using constant space complexity. Example Given 1-3->2->null, sort it to 1->2->3->null. Note 這道題目可以用分治法來做,首先...
摘要:求數組交集不同解法小結聲明文章均為本人技術筆記,轉載請注明出處求數組交集要求元素不重復,給出兩個數組,求二者交集且元素不重復,查找會超時解法一排序二分查找算法超時主要發生在大數組查找過程,因此采用二分查找提升查找效率,交集用保存實現去重解法 LintCode547/548_求數組交集不同解法小結 [TOC] 聲明 文章均為本人技術筆記,轉載請注明出處:[1] https://segme...
閱讀 2270·2021-09-28 09:36
閱讀 2034·2021-09-22 15:14
閱讀 3633·2019-08-30 12:47
閱讀 3042·2019-08-30 12:44
閱讀 1237·2019-08-29 17:06
閱讀 541·2019-08-29 14:12
閱讀 981·2019-08-29 14:01
閱讀 2584·2019-08-29 12:17
极致性价比!云服务器续费无忧!
Tesla A100/A800、Tesla V100S等多种GPU云主机特惠2折起,不限台数,续费同价。
NVIDIA RTX 40系,高性价比推理显卡,满足AI应用场景需要。
乌兰察布+上海青浦,满足东推西训AI场景需要