Leetcode | Sort List
9549 단어 LeetCode
mergesort,heapsort,quicksort는 모두 O(nlgn)지만,mergesort와quicksort는 모두 귀속적이며,constantspace가 아니라,heapsort는 무작위 접근이 있어야 합니다.
mergesort의bottom up은 상수 공간을 실현할 수 있습니다.체인 시계에도 적용됩니다.
그룹이라면 heapsort도 사용할 수 있습니다.
1 /**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode(int x) : val(x), next(NULL) {}
7 * };
8 */
9 class Solution {
10 public:
11 // merge two list, and return last element (not NULL)
12 ListNode* merge(ListNode *nh, ListNode *p1, ListNode *p2) {
13 while (p1 || p2) {
14 if (p1 && (p2 == NULL || p1->val < p2->val)) {
15 nh->next = p1;
16 p1 = p1->next;
17 } else {
18 nh->next = p2;
19 p2 = p2->next;
20 }
21 nh = nh->next;
22 }
23 return nh;
24 }
25
26 // get length of list
27 int getLength(ListNode *head) {
28 int n = 0;
29 while (head) {
30 n++;
31 head = head->next;
32 }
33 return n;
34 }
35
36 ListNode *sortList(ListNode *head) {
37 int n = getLength(head);
38 ListNode *p1, *p2, *tmp, *newH1, *tail;
39
40 // merge sort, bottom up
41 for (int l = 1; l < n; l *= 2) {
42 p1 = head;
43 tail = head = NULL; // head of the whole list
44 while (p1) {
45 p2 = p1;
46 for (int i = 1; i < l && p2; ++i) {
47 p2 = p2->next;
48 }
49 if (!p2) break;
50 tmp = p2->next;
51 p2->next = NULL; // set tail of list 1 to NULL
52 p2 = tmp;
53 for (int i = 1; i < l && tmp; ++i) {
54 tmp = tmp->next;
55 }
56 if (tmp) {
57 newH1 = tmp->next; // get next head of list 1
58 tmp->next = NULL; // set tail of list 2 to NULL
59 } else {
60 newH1 = NULL;
61 }
62 ListNode h(0);
63 ListNode *last = merge(&h, p1, p2);
64 if (tail) tail->next = h.next; // connect the sorted part with the current two list
65 if (!head) head = h.next;
66 tail = last;
67 last->next = newH1;
68 p1 = newH1;
69 }
70 }
71 return head;
72 }
73 };
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.