首页 > 代码库 > Leetcode | Sort List

Leetcode | Sort List

2024-07-10 20:12:14   219人阅读

Sort a linked list in O(n log n) time using constant space complexity.

merge sort、heap sort和quick sort都是O(nlgn)，但是mergesort和quicksort都是递归的，不是constant space的，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 list27     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 up41         for (int l = 1; l < n; l *= 2) {42             p1 = head;43             tail = head = NULL; // head of the whole list44             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 NULL52                 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 158                     tmp->next = NULL; // set tail of list 2 to NULL59                 } 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 list65                 if (!head) head = h.next;66                 tail = last;67                 last->next = newH1;68                 p1 = newH1;69             }70         }71         return head;72     }73 };

 


联系
我们