leetcode 148 Sort List

2022-11-24 14:51:24 字數 2821 閱讀 8978

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

example 3:

input: head = 

output:

constraints:

題目難度:簡單(遞迴式歸併),中等(非遞迴歸併)

題目大意:給一個連結串列排序,並要求常數空間複雜度$o(1)$,$o(nlogn)時間複雜度$

思路:常用的快排和歸併排序,快排在有些情況下的時間複雜度是$(n^2)$,在連結串列情況下不方便。選擇第一個節點為樞紐值。

歸併排序時間複雜度是$o(nlogn)$,用遞迴方法實現的方法,空間複雜度是o(logn)(棧)。所以按照提議應該選擇迭代式的歸併排序,可以實現$o(1)$空間複雜度(由於是連結串列,在歸併的時候可以不用先new陣列作為輔助)。

版本一:遞迴式的歸併排序c++**:

1/**

2* definition for singly-linked list.

3* struct listnode

7* listnode(int x) : val(x), next(nullptr) {}

8* listnode(int x, listnode *next) : val(x), next(next) {}

9* };

10*/

11class

solution else

27 tail->next =null;28}

29if (nullptr !=tmp1)

30 tail->next =tmp1;

31else

32 tail->next =tmp2;

33return res->next;34}

35//

找到後一半連結串列,並返回後一半連結串列的頭指標,同時將前一半連結串列的尾結點指標指向null。

36 listnode* splitlist(listnode *head)

43 listnode *mid = midprev->next;

44 midprev->next =nullptr;

45return

mid;46}

47//

void printlist(listnode *head)

55//

cout << endl;

56//}57

public

:58 listnode* sortlist(listnode*head)

69 };

版本二:迭代式的歸併排序c++**:

1

class

solution

10if (midprev->next) 13}

14 listnode *mid = midprev->next;

15 nextsublist = end->next;

16 midprev->next =nullptr;

17 end->next =nullptr;

18return

mid;19}

2021

//合併兩個有序連結串列

22void mergelist(listnode *front, listnode *rear) else

35 newtail->next =null;36}

37if (nullptr !=tmp1)

38 newtail->next =tmp1;

39else

40 newtail->next =tmp2;

41while (newtail->next)

44 tail->next = res->next;

45 tail =newtail;46}

47int gcount(listnode *head)

54return

cnt;55}

56//

void printlist(listnode *head)

64//

cout << endl;

65//}66

public

:67 listnode *tail = new listnode(); //

用於始終指向已排序部分的尾結點

68 listnode *nextsublist = new listnode(); //

始終指向待排序部分的頭結點

6970 listnode* sortlist(listnode*head)

82 listnode *mid =split(start, size);

83mergelist(start, mid);

84 start =nextsublist;85}

86 start = dummyhead->next;87}

88return dummyhead->next;

89}

90 };

Leetcode148 Sort List

sort list 在leetcode 裡面,因為只有歸併排序的時間複雜度為o 1 所以快速排序用不了,前面兩個都沒用直接看最後一個歸併排序。氣泡排序 超時了 public listnode sortlist listnode head current head int pre while coun...

148 Sort List

一 題目 1 審題 2 分析 將一個連結串列節點進行排序,時間複雜度為 nlogn,且使用常數的空間複雜度。二 解答 1 思路 採用歸併排序的思想。將連結串列進行切割 將切割的連結串列進行排序 合併切割的連結串列。public listnode sortlist listnode head prev...

LeetCode Sort List

question sort a linked list in o n log n time using constant space complexity.solution 看到對連結串列的排序,時間複雜度o n log n 首先想到的就是歸併排序。但是這裡其中有兩個技巧 就是將兩個連結串列分開的時...