摘要:題目解答對(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)解的解釋)
根據(jù)時(shí)間復(fù)雜度的要求,很容易想到應(yīng)該用merge sort的方法來(lái)做,那么就有兩個(gè)步驟,分和法。先把整個(gè)list分成兩部分,這里可以用找中間值的方法,在找中間值的同時(shí),標(biāo)記一下中間值的前一個(gè)node,也就是第一個(gè)list的最后一個(gè)node,然后找到中間值之前,將最后一個(gè)node的下一位標(biāo)記為null,就成功地將這個(gè)list分成了兩部分;接下來(lái)是merge, 那就建一個(gè)新的list,將兩個(gè)sort好的list按最小數(shù)的大小依次放進(jìn)新list中,最后返回merge的list。解法如下:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; //seperate the list into two parts //Track the last node of first list and point the end to null ListNode prev = null; ListNode 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 l = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { l.next = l1; l1 = l1.next; } else { l.next = l2; l2 = l2.next; } l = l.next; } while (l1 != null) { l.next = l1; l1 = l1.next; l = l.next; } while (l2 != null) { l.next = l2; l2 = l2.next; l = l.next; } return dummy.next; } }
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/64846.html
摘要:題目分析一看到問(wèn)題,而且時(shí)間復(fù)雜度要求又是,很自然地就會(huì)想到數(shù)組時(shí),如下這道題要求是,所以在上面的基礎(chǔ)上還要進(jìn)行一些額外操作找到的中點(diǎn),使用快慢指針?lè)āP枰⒁獾氖牵业街悬c(diǎn)后要把鏈表分成兩段,即兩個(gè)鏈表。這部分代碼應(yīng)該近似于這道題的答案。 Sort a linked list in O(n log n) time using constant space complexity. 題...
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...
摘要:題目要求用的時(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ù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個(gè)數(shù)字。總結(jié)本題和三數(shù)之和很像,都是三個(gè)數(shù)加和為某一個(gè)值。所以我們可以使用歸并排序來(lái)解決這個(gè)問(wèn)題。注意因?yàn)闅w并排序需要遞歸,所以空間復(fù)雜度為 ...
摘要:將返回結(jié)果限制為前個(gè)。所以,聚合的結(jié)果必須要限制在以內(nèi)支持的最大響應(yīng)消息大小。包含字段和排除字段的規(guī)則與常規(guī)查詢中的語(yǔ)法一致。改變字符大小寫(xiě)的操作,只保證對(duì)羅馬字符有效。只對(duì)羅馬字符組成的字符串有效。 上一篇文章:MongoDB指南---15、特殊的索引和集合:地理空間索引、使用GridFS存儲(chǔ)文件下一篇文章:MongoDB指南---17、MapReduce 如果你有數(shù)據(jù)存儲(chǔ)在Mon...
閱讀 3043·2021-11-25 09:43
閱讀 1626·2021-11-24 11:15
閱讀 2359·2021-11-22 15:25
閱讀 3501·2021-11-11 16:55
閱讀 3240·2021-11-04 16:10
閱讀 2773·2021-09-14 18:02
閱讀 1685·2021-09-10 10:50
閱讀 1070·2019-08-29 15:39