DHU高级程序语言设计-leetcode刷题148排序链表

148排序链表

题目描述：
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
输入范例：
5
-1 5 3 4 0
输出范例：
head–>-1–>0–>3–>4–>5–>tail
思路：
依我浅薄的知识…首先想到了快排 但是通过看题解了解快排时间复杂度并不是一直都是O(n log n)
所以题解给的排序方法的是归并排序
归并排序有两种实现方法：1、递归 2、迭代
递归就是传统思路，迭代算是新学的
附链接：https://leetcode-cn.com/problems/sort-list/solution/148-pai-xu-lian-biao-bottom-to-up-o1-kong-jian-by-/
迭代代码：

class Solution {
public:
 /*ut(l, n)，可能有些同学没有听说过，它其实就是一种 split 操作，即断链操作。
 不过我感觉使用 cut 更准确一些，它表示，将链表 l 切掉前 n 个节点，并返回后半部分的链表头。
 */ 
    ListNode* cut(ListNode* head, int n)
    {
        auto p=head;
        while(p!=nullptr&&--n)
        {
            p=p->next;
        }
        if (!p) return nullptr;
        auto next=p->next;
        p->next=nullptr;
        return next;
    }
    ListNode* sortList(ListNode* head) {
        ListNode dummyHead(0);//临时头结点 
        dummyHead.next=head;
        auto p=head;
        int length=0;
        while(p!=nullptr)//求链表长度 
        {
            ++length;
            p=p->next;
        }
        for(int size=1;size<length;size*=2)
        {
            auto cur=dummyHead.next;
            auto tail=&dummyHead;
            while(cur)//依次从2、4、6、8......到length长度 开始归并 
            {
                auto left=cur;
                auto right=cut(left, size);
                cur=cut(right, size);
                tail=merge(left, tail, right);//传入上一个tail，返回新tail
            }
        }
        return dummyHead.next;
    }
    ListNode* merge(ListNode* left,ListNode* head, ListNode* right)
    {
        auto p=head;
        while(left&&right)//两两归并 头结点始终指向较小的那个结点 
        {
            if(left->val<=right->val)
            {
                p->next=left;
                left=left->next;
                p=p->next;
            }
            else
            {
                p->next=right;
                right=right->next;
                p=p->next;
            }
        }
        p->next=right?right:left;
        while(p->next!=nullptr)
        {
            p=p->next;
        }
        return p;
    }
};

供自己学习知识点：
1、cut函数
2、merge函数
3、临时头结点dummyHead