IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 归并排序 - 排序链表 -> 正文阅读

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

题目:给你链表的头结点 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;
    
}

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-12-25 11:33:24  更:2022-12-25 11:38:20 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年7日历 -2024/7/19 13:05:31-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码