递归建表
是不是很优雅!
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
ListNode* Create(int n) {
if(!n) return NULL;
int num;
cin >> num;
auto p = new ListNode(num, Create(n - 1));
return p;
}
插入排序
自己鼓捣的,不知道叫什么名字,有点插入的味道,姑且叫做插入排序吧
核心思路:
=> 新开一个哨兵结点dummy,后面接有序链表;
待排序链表记录当前结点(p)及其后驱结点(last),然后断开两者联系(p->next = NULL);
接着,将p插入到dummy后面的结点中的合适位置(通过while+ if判断);
p = last,不断迭代。
List DSortList(List head) {
if(!head || !head->next) return head;
List last = head->next;
head->next = NULL;
List dummy = (List)malloc(sizeof(Node));
dummy->aver = INT_MAX;
dummy->next = head;
List p = last;
while(p) {
last = p->next;
p->next = NULL;
List temp = dummy;
while(temp) {
if(temp->next == NULL || (temp->aver >= p->aver && temp->next->aver <= p->aver) ) {
p->next = temp->next;
temp->next = p;
break;
}
temp = temp->next;
}
p = last;
}
return dummy->next;
}
leetcode上看到的比较优雅的解法:
ListNode* insertionSortList(ListNode* head) {
auto dummy = new ListNode(-1, NULL);
auto p = head;
while(p) {
auto cur = dummy;
while(cur->next && cur->next->val <= p->val) cur = cur->next;
auto next = p->next;
p->next = cur->next;
cur->next = p;
p = next;
}
return dummy->next;
}
本质和我的思路一样,但是代码更加短小精悍,值得推荐
归并排序
归并排序其实是链表排序的主流方法(时间复杂度是O(nlogn))。 归并主要分为分割和合并两大部分,入栈的时候分割,出栈的时候合并,这也是归并常常采用递归实现的原因
class Merge{
public:
ListNode* sort(ListNode* head) {
if(!head || !head->next) return head;
return mergeSort(head);
}
private:
ListNode* mergeSort(ListNode* head) {
if(!head || !head->next) return head;
auto slow = head, fast = head->next;
while(fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
auto rightHead = slow->next;
// 记得断开左右两个链表的联系
slow->next = NULL;
auto left = mergeSort(head);
auto right = mergeSort(rightHead);
return merge(left, right);
}
ListNode* merge(ListNode* p1, ListNode* p2) {
auto dummy = new ListNode(-1, NULL);
auto p = dummy;
while(p1 && p2) {
if(p1->val < p2->val) {
p->next = p1;
p1 = p1->next;
}else {
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
p->next = p1 ? p1 : p2;
return dummy->next;
}
};