[数据结构与算法]归并排序 - 排序链表

题目：给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

要求：在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

1. 由于时间复杂度要在o(n log n)内 所以冒泡排序就不在选择范围内了 这里采用归并排序。
2. 归并排序分为 迭代法 和 递归法 下面俩种方法的代码都将展示。
3. 递归的核心思路就是:二分法
   从中间切割 然后左右俩边的一路按中切割到最小单位 然后排序返回
   举例 42507163
   42507163
   4250 7163
   42 50 71 63 切割到最小单位排序
   24 05 17 36 再合并排序
   0245 1376
   01234567
4. 迭代法是在链表长度内进行切割
   先 2 2比较完后排序 再 4 4比较 再8 8…
   举例: 42507163
   先按42 50 71 63切割后排序得 24 05 17 36
   再按2405 1736切割后排序 得 0245 1367
   最后再按02451367比较排序 得 01234567

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* FindLinkMid(struct ListNode* head) // 快慢指针法寻中点
{
    if (head == NULL) {
        return head;
    }

    struct ListNode* fast = head->next; // 快指针, 从第二个指针开始每次走俩步
    struct ListNode* slow = head;       // 慢指针, 从头开始每次走一步

    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
    }

    return slow;
}

struct ListNode* Merger(struct ListNode* left, struct ListNode* right) // 有序链表归并排序
{
    struct ListNode* head = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode* temp = head;

    head->next = NULL;

    while (left != NULL && right != NULL) { //左右有序链表比较后, 较小值归入新建链表
    
        if (left->val <= right->val) {
            temp->next = left;
            left = left->next;
        } else {
            temp->next = right;
            right = right->next;
        }

        temp = temp->next;
    }

    if (left != NULL) { // 由于是有序, 可把剩余内容归入新链表
        temp->next = left;
    }

    if (right != NULL) { // 同上
        temp->next = right;
    }

    return head->next;
}


//递归的核心思路就是:二分法
//从中间切割 然后左右俩边的一路按中切割到最小单位 然后排序返回
//举例 42507163
//      42507163
//  4250        7163
//  42  50  71  63  切割到最小单位排序
//  24  05  17  36   再合并排序
//  0245 1376
//  01234567

struct ListNode* MergerSort_Recursion(struct ListNode* head) //归并排序-递归
{
    if (head == NULL || head->next == NULL) {//当链表被分割的只剩一个时 无需排序直接返回
        return head;
    }

    struct ListNode* mid = FindLinkMid(head); //找到中节点
    struct ListNode* next = mid->next; // 存储右边节点

    mid->next = NULL; // 把链表从中间分割开
    struct ListNode* left  = MergerSort_Recursion(head); // 左排序
    struct ListNode* right = MergerSort_Recursion(next); // 右排序 

    return Merger(left, right); // 合并
}

struct ListNode* Cut_List(struct ListNode* head, int cut) // 切割掉链表head 前cut个
{
    while (head!=NULL && --cut) {
        head = head->next;
    }

    if (head == NULL) {
        return NULL;
    }

    struct ListNode*temp = head->next;
    head->next = NULL;

    return temp;
}

// 迭代法是在链表长度内进行切割 
// 先 2 2比较完后排序 再 4 4比较 再8 8...
// 举例: 42507163
// 先按42 50 71 63切割后排序得 24 05 17 36
// 再按2405 1736切割后排序 得 0245 1367
// 最后再按02451367比较排序 得 01234567

struct ListNode* MergerSort_Iteration(struct ListNode* head) //归并排序-迭代
{
    if (head == NULL || head->next == NULL) {//当链表长度小于等于1 直接返回
        return head;
    }

    int len = 1;
    struct ListNode* temp = head;
    while(temp->next != NULL) { //计算链表长度
        len++;
        temp = temp->next;
    }
    
    struct ListNode* dummy = (struct ListNode *)malloc(sizeof(struct ListNode)); //排序后的链表头
    dummy->next = head;
    
    for (int cut = 1; cut < len; cut<<=1) {     //循环遍历链表 log2(len)次
        struct ListNode* curr = dummy->next;    // 当前链表头
        struct ListNode* tail = dummy;          // 临时链表 用于拼接排序合并后的链表
        while (curr != NULL) {                  //遍历当前链表
            struct ListNode* left = curr;
            struct ListNode* right = Cut_List(left, cut);   //把左边切割出去 获取右边首地址
            curr = Cut_List(right, cut);        //把右边切割出去 留下剩下未排序的链表下轮继续切割排序
            tail->next = Merger(left, right);   //合并排序
            while(tail->next != NULL) {         //尾插法 把合并排序后的链表插入新链表temp
                tail = tail->next;
            }
            
        }
    }

    return dummy->next;
    
}