首页 > 其他分享 >排序链表

排序链表

时间:2024-04-01 16:33:38浏览次数:20  
标签:ListNode head2 head1 nullptr next 链表 curr 排序

1、非递归

// 递归的归并排序
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr)
            return head;
        int length = 0;
        ListNode* node = head;
        while (node != nullptr) {
            length++;
            node = node->next;
        }
        ListNode* dummyHead = new ListNode(0, head);
        for (int subLength = 1; subLength < length; subLength *= 2) {
            ListNode *prev = dummyHead, *curr = dummyHead->next;
            while (curr != nullptr) {
                ListNode* head1 = curr;
                // 取子长度的链表
                for (int i = 1; i < subLength && curr->next != nullptr; ++i)
                    curr = curr->next;
                ListNode* head2 = curr->next;
                curr->next = nullptr;
                curr = head2;
                if (curr == nullptr) {
                    ListNode* merged = merge(head1, head2);
                    prev->next = merged;
                    break;
                }
                // 不只是取第一个和第二个链表的头节点,需要记录第二个链表的末尾,不然后面很难遍历
                for (int i = 1; i < subLength && curr->next != nullptr; ++i) {
                    curr = curr->next;
                }
                // 下一次遍历从下一个结尾
                ListNode* next = nullptr;
                if (curr->next != nullptr) {
                    next = curr->next;
                    curr->next = nullptr;
                }
                ListNode* merged = merge(head1, head2);
                prev->next = merged;
                while (prev->next != nullptr) {
                    prev = prev->next;
                }
                curr = next;
            }
        }
        return dummyHead->next;
    }
    // 两两合并
    ListNode* merge(ListNode* head1, ListNode* head2) {
        ListNode* dummmy = new ListNode();
        ListNode* p = dummmy;
        while (head1 && head2) {
            if (head1->val < head2->val) {
                p->next = head1;
                head1 = head1->next;
            } else {
                p->next = head2;
                head2 = head2->next;
            }
            p = p->next;
        }
        if (head1) {
            p->next = head1;
        } else {
            p->next = head2;
        }
        p = dummmy->next;
        delete dummmy;
        return p;
    }
};

2、递归

//递归的归并排序
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return sortList(head, nullptr);
    }
    ListNode* sortList(ListNode* head1, ListNode* head2)
    {
        //从节点head1到节点head2进行排序
        if (head1 == nullptr)
            return head1;
        if (head1->next == head2)
        {
            head1->next = nullptr; //因为从begin,mid) [mid,last]
            return head1;
        }
        //取终点再次进行折半
        ListNode* fast = head1, * slow = head1;
        while (fast != head2)
        {
            fast = fast->next;
            slow = slow->next;
            if (fast != head2)
                fast = fast->next;
        }
        ListNode* l1 = sortList(head1, slow);
        ListNode* l2 = sortList(slow, head2);
        return merge(l1, l2);
    }
    //两两合并
    ListNode* merge(ListNode* head1, ListNode* head2)
    {
        ListNode* dummmy = new ListNode();
        ListNode* p = dummmy;
        while (head1 && head2)
        {
            if (head1->val < head2->val)
            {
                p->next = head1;
                head1 = head1->next;
            }
            else
            {
                p->next = head2;
                head2 = head2->next;
            }
            p = p->next;
        }
        if (head1)
            p->next = head1;
        else
            p->next = head2;
        p = dummmy->next;
        delete dummmy;
        return p;
    }
};

 

标签:ListNode,head2,head1,nullptr,next,链表,curr,排序
From: https://www.cnblogs.com/Kellen-Gram/p/18108777

相关文章

  • 关于排序稳定性
    堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法,而冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。首先,排序算法的稳定性大家应该都知道,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简......
  • 23--归并排序
     算法描述:就是将两个有序的合并为一个较大的有序的,直到完全有序为止,也称为2路归并。其时间复杂度是,空间复杂度是,并且稳定。代码如下:#include<stdio.h>#include<malloc.h>#include<assert.h>//一趟归并(自己使用,用static),一趟归并的时间复杂度为O(n)//gap:归并段的长度......
  • Python数据结构与算法——数据结构(链表、哈希表、树)
    目录链表  链表介绍  创建和遍历链表  链表节点插入和删除  双链表  链表总结——复杂度分析哈希表(散列表)哈希表介绍哈希冲突哈希表实现哈希表应用树树树的示例——模拟文件系统二叉树二叉树的链式存储 二叉树的遍历二叉搜索树插入......
  • 【数据结构】线性表-单链表
    编程语言:C++前言:节点:节点是链表的一个基本单元,包含两部分——数据域和指针域,数据域用于存储数据,指针域存储下一个节点的地址,形成链结。什么是单链表:n个节点链结成一个链表,即为线性表(a1,a2,a3……)的链式存储结构,每个节点只包含一个指针域的链表叫做单链表。链表组成:头节点、......
  • 搜索与图论(五)拓扑排序---以题为例
    给定一个 n 个点 m 条边的有向图,点的编号是 1 到 n,图中可能存在重边和自环。请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 −1。若一个由图中所有点构成的序列 A 满足:对于图中的每条边 (x,y),x 在 A 中都出现在 y 之前,则称 A 是该图的一个拓扑序......
  • 快速排序(C语言实现)此文章由vivo的AI蓝心小v生成
    当然可以。快速排序是一种非常高效的排序算法,由英国计算机科学家霍尔(C.A.R.Hoare)于1962年提出。它的基本思想是采用分治法(DivideandConquer)来进行排序。###快速排序的基本步骤:1.**选择基准值(Pivot)**:从待排序的序列中选取一个元素作为基准值。这个元素可以是序列的第一......
  • 多目标应用:基于非支配排序的蜣螂优化算法(Non-Dominated Sorting Dung beetle optimize
    一、柔性作业车间调度问题柔性作业车间调度问题(FlexibleJobSchedulingProblem,FJSP)的描述如下:n个工件{J,J......
  • 拓扑排序的模板
    拓扑排序的模板,csdn:https://blog.csdn.net/weixin_43872728/article/details/98981923#include<iostream>#include<vector>#include<cstdio>#include<queue>#include<cstring>#include<algorithm>usingnamespacestd;intin[10......
  • 数据结构-C语言描述(队列的链表实现)
    概述在日常生活中,先进先出似乎更加符合我们的日常认知。 排队的人群中,队首的人总是先离开,而队尾的人总是后离开。1.队列的基本原理和操作我们知道队列也是一种线性表,而今天我们就用非顺序储存结构(链表)来实现它。首先我们先明确队列的基本操作原理:因为同时涉及到队首和队......
  • 如何实现快速排序算法?
    如何实现快速排序算法?如何实现快速排序算法?......