資訊專(zhuān)欄INFORMATION COLUMN
摘要：題目要求用的時(shí)間復(fù)雜度和的空間復(fù)雜度檢索一個(gè)鏈表。那么問(wèn)題就歸結(jié)為如何將鏈表分為大小相近的兩半以及如何將二者合并。之后再對(duì)折斷的鏈表分別進(jìn)行計(jì)算從而確保每一段內(nèi)的元素為有序的。
題目要求
Sort a linked list in O(n log n) time using constant space complexity.
用O(n log n)的時(shí)間復(fù)雜度和O(1)的空間復(fù)雜度檢索一個(gè)鏈表。
思路和代碼在給出了明確的時(shí)間復(fù)雜度和空間復(fù)雜度后，我第一個(gè)想到的就是利用divide and conquer 方法進(jìn)行排序。那么問(wèn)題就歸結(jié)為如何將鏈表分為大小相近的兩半以及如何將二者合并。
了解利用分治法對(duì)數(shù)組進(jìn)行排序的童鞋應(yīng)該知道，我們會(huì)根據(jù)數(shù)組的下標(biāo)將數(shù)組取一半分別進(jìn)行排序后，再將排序好的二者進(jìn)行合并。
那么將鏈表分為大小相近的兩部分則需要我們用三個(gè)指針來(lái)進(jìn)行。分別是prev, slow和fast，其中fast指針每次往前跑兩步，slow往前跑一步，這樣確保slow指針是第二部分開(kāi)頭的第一個(gè)指針，而prev則是slow指針的前一個(gè)指針。prev指針是用來(lái)折斷鏈表的。
ListNode prev = null, slow = head, fast = head;
while(fast!=null && fast.next!=null){
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
之后再對(duì)折斷的鏈表分別進(jìn)行計(jì)算從而確保每一段內(nèi)的元素為有序的。
之后我們需要將相鄰的兩段鏈表進(jìn)行合并，這個(gè)就很簡(jiǎn)單了。只需要另設(shè)一個(gè)頭指針，并每次比較兩段的當(dāng)前節(jié)點(diǎn)，取較小的節(jié)點(diǎn)加入頭指針即可。
所有代碼如下：
public ListNode sortList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode prev = null, slow = head, fast = head;
while(fast!=null && fast.next!=null){
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
return merge(l1, l2);
}
public ListNode merge(ListNode l1, ListNode l2){
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while(l1!=null && l2!=null){
if(l1.val < l2.val){
ListNode tmp = l1.next;
cur.next = l1;
l1.next = null;
l1 = tmp;
}else{
ListNode tmp = l2.next;
cur.next = l2;
l2.next = null;
l2 = tmp;
}
cur = cur.next;
}
if(l1==null) cur.next = l2;
else cur.next = l1;
return dummy.next;
}
想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/68184.html
Problem Sort a linked list in O(n log n) time using constant space complexity. Example 1: Input: 4->2->1->3 Output: 1->2->3->4 Example 2: Input: -1->5->3->4->0 Output: -1->0->3->4->5 Solution Merge S...
摘要：有效三角形的個(gè)數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個(gè)數(shù)字?？偨Y(jié)本題和三數(shù)之和很像，都是三個(gè)數(shù)加和為某一個(gè)值。所以我們可以使用歸并排序來(lái)解決這個(gè)問(wèn)題。注意因?yàn)闅w并排序需要遞歸，所以空間復(fù)雜度為 ...
摘要：題目解答對(duì)于中第二個(gè)最優(yōu)解的解釋根據(jù)時(shí)間復(fù)雜度的要求，很容易想到應(yīng)該用的方法來(lái)做，那么就有兩個(gè)步驟，分和法。 題目：Sort a linked list in O(n log n) time using constant space complexity. 解答：(對(duì)于discuss中第二個(gè)最優(yōu)解的解釋?zhuān)└鶕?jù)時(shí)間復(fù)雜度的要求，很容易想到應(yīng)該用merge sort的方法來(lái)做，那么就有兩個(gè)...
摘要：題目分析一看到問(wèn)題，而且時(shí)間復(fù)雜度要求又是，很自然地就會(huì)想到數(shù)組時(shí)，如下這道題要求是，所以在上面的基礎(chǔ)上還要進(jìn)行一些額外操作找到的中點(diǎn)，使用快慢指針?lè)āＰ枰⒁獾氖?，找到中點(diǎn)后要把鏈表分成兩段，即兩個(gè)鏈表。這部分代碼應(yīng)該近似于這道題的答案。 Sort a linked list in O(n log n) time using constant space complexity. 題...
摘要：方法上沒(méi)太多難點(diǎn)，先按所有區(qū)間的起點(diǎn)排序，然后用和兩個(gè)指針，如果有交集進(jìn)行操作，否則向后移動(dòng)。由于要求的，就對(duì)原數(shù)組直接進(jìn)行操作了。時(shí)間復(fù)雜度是的時(shí)間。 Problem Given a collection of intervals, merge all overlapping intervals. Example Given intervals => merged intervals...
閱讀 2689·2021-11-18 10:02
閱讀 3417·2021-09-28 09:35
閱讀 2598·2021-09-22 15:12
閱讀 757·2021-09-22 15:08
閱讀 3123·2021-09-07 09:58
閱讀 3479·2021-08-23 09:42
閱讀 738·2019-08-30 12:53
閱讀 2087·2019-08-29 13:51
