链接
我写的错误代码:
class Solution {
public:ListNode* sortList(ListNode* head) {if (!head || !head->next)return head;ListNode* fast = head;ListNode* slow = head;while (fast&&fast->next) {fast = fast->next->next;slow = slow->next;}ListNode* p = sortList(head);ListNode* q = sortList(slow);return merge(p, q);}ListNode* merge(ListNode* p, ListNode* q) {ListNode* head = new ListNode(-1);while (p && q) {if (p->val <= q->val) {ListNode* cur = p->next;p->next = head->next;head->next = p;p = p->next;} else {ListNode* cur = q->next;q->next = head->next;head->next = q;q = q->next;}}ListNode* tail = head;while (tail->next) {tail = tail->next;}tail->next = p ? p : q;return head->next;}
};
正确代码如下:
/*** Definition for singly-linked list.* 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) {}* };*/
class Solution {
public:ListNode* sortList(ListNode* head) {int n = 0;for(auto p = head;p;p = p->next)++n;for(int i = 1;i<n;i*=2){//刚开始每段只有一个节点,最后一次每段有大约一半节点,合并成最后的答案auto dummy = new ListNode(-1),cur = dummy;for(int j = 1;j<=n;j+=i*2){auto p = head,q = p;for(int k = 0;k<i&&q;k++) q = q->next;auto o = q;for(int k = 0;k<i&&o;k++)o = o->next;int l = 0,r = 0;while(l<i && r<i && p && q){if(p->val<=q->val)cur = cur->next = p,p = p->next,l++;else cur = cur->next = q,q = q->next,r++;}while(l<i && p){cur = cur->next = p;p = p->next;l++;}while(r<i && q){cur = cur->next = q;q = q->next;r++;}head = o;}cur->next = nullptr;head = dummy->next;dummy->next = nullptr;//delete dummy;//}return head;}
};
这是自底向上归并排序写法。
图示:
上图cur也要跟随移动。
第二轮:
总体图示就这样的。q是依靠p推出来的,刚开始跳1步,然后跳2步........
o是为了记录下一次应该继续排序的位置。
dummy是一个虚拟头结点,cur用来维护它的尾,至于谁往cur->next插入,要看p q指向的节点谁的值小。
每一轮完了后,让head重新回归dummy的next,然后cur->next=nullptr;即将尾置空。