資訊專欄INFORMATION COLUMN
摘要：題目分析一看到問(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.
一看到sort問(wèn)題，而且時(shí)間復(fù)雜度要求又是O(n log n)，很自然地就會(huì)想到Merge sort. Merge sort數(shù)組時(shí)，pseudo code如下：
func mergesort( var a as array ) if ( n == 1 ) return a var l1 as array = a[0] ... a[n/2] var l2 as array = a[n/2+1] ... a[n] l1 = mergesort( l1 ) l2 = mergesort( l2 ) return merge( l1, l2 ) end func func merge( var a as array, var b as array ) var c as array while ( a and b have elements ) if ( a[0] > b[0] ) add b[0] to the end of c remove b[0] from b else add a[0] to the end of c remove a[0] from a while ( a has elements ) add a[0] to the end of c remove a[0] from a while ( b has elements ) add b[0] to the end of c remove b[0] from b return c end func(Reference: http://www.algorithmist.com/i... )
這道題要求是sort linked list，所以在上面pseudo code的基礎(chǔ)上還要進(jìn)行一些額外操作：
找到List的中點(diǎn)，使用快慢指針?lè)ā?/p>
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
需要注意的是，找到中點(diǎn)后要把鏈表分成兩段，即: slow.next = null;
Merge兩個(gè)鏈表。這部分代碼應(yīng)該近似于merge 2 sorted lists這道題的答案。
代碼/**
* 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;
}
// find the mid point of the linked list
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode head2 = slow.next;
slow.next = null;
// if there"s only 1 element in the list, continue splitting
ListNode list1 = null;
ListNode list2 = null;
if (head != head2) {
list1 = sortList(head);
list2 = sortList(head2);
}
// merge 2 lists
return mergeList(list1, list2);
}
// merge 2 lists. reference: Merge 2 Linked List
public ListNode mergeList(ListNode head1, ListNode head2) {
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
ListNode dummy = new ListNode(0);
ListNode p = dummy;
while (head1 != null && head2 != null) {
if (head1.val <= head2.val) {
p.next = head1;
p = p.next;
head1 = head1.next;
} else {
p.next = head2;
p = p.next;
head2 = head2.next;
}
}
if (head1 != null) {
p.next = head1;
}
if (head2 != null) {
p.next = head2;
}
return dummy.next;
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度 O(n log n)
空間復(fù)雜度 O(1)
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66896.html
摘要：題目解答對(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è)...
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ǔ)法一致。改變字符大小寫的操作，只保證對(duì)羅馬字符有效。只對(duì)羅馬字符組成的字符串有效。 上一篇文章：MongoDB指南---15、特殊的索引和集合：地理空間索引、使用GridFS存儲(chǔ)文件下一篇文章：MongoDB指南---17、MapReduce 如果你有數(shù)據(jù)存儲(chǔ)在Mon...
閱讀 1807·2023-04-26 01:44
閱讀 1222·2021-11-12 10:34
閱讀 1611·2021-09-09 09:33
閱讀 1740·2019-08-30 15:44
閱讀 2903·2019-08-30 13:49
閱讀 2199·2019-08-29 15:26
閱讀 953·2019-08-26 13:30
閱讀 1420·2019-08-23 18:15
