LeetCode 算法:排序链表 c++

2024-06-22 23:52

本文主要是介绍LeetCode 算法:排序链表 c++,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

原题链接🔗:排序链表
难度:中等⭐️⭐️

题目

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

示例 1
在这里插入图片描述

输入:head = [4,2,1,3]
输出:[1,2,3,4]

示例 2
在这里插入图片描述

输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]

示例 3

输入:head = []
输出:[]

提示

  • 链表中节点的数目在范围 [0, 5 * 104] 内
  • -105 <= Node.val <= 105

进阶:你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?

题解

  1. 题解

LeetCode 上的 “Sort a linked list” 题目要求我们对链表进行排序。这个问题可以通过多种排序算法来解决,但是使用归并排序是最有效的方法,因为链表不适合使用快速排序或堆排序这类需要随机访问数据的算法。以下是使用归并排序对链表进行排序的解题思路:

  • 选择排序算法:由于链表的特性,归并排序是一个很好的选择。归并排序在链表上的实现相对简单,因为它不需要随机访问元素,只需要遍历链表。

  • 归并排序链表的步骤: 归并排序链表的步骤如下:

    • 分割链表:找到链表的中点,将链表分为两个子链表。
    • 递归排序:对两个子链表递归地进行排序。
    • 合并链表:合并两个已排序的子链表。
  • 实现分割链表:使用快慢指针法来找到链表的中点:

    • 初始化两个指针 slow 和 fast,都指向头节点。
    • fast 每次移动两步,slow 每次移动一步。
    • 当 fast到达链表末尾时,slow 将位于中点。
  • 实现递归排序 :递归地对分割后的两个子链表进行排序:

    • 如果子链表为空或只有一个节点,直接返回该子链表。
    • 否则,分割子链表并递归排序。
  • 实现合并链表:合并两个有序链表:

    • 创建一个哑节点(dummy node),用于简化边界条件的处理。
    • 使用一个指针 tail 指向哑节点,用于构建合并后的链表。
    • 比较两个链表头部的节点值,将较小的节点添加到合并后的链表中,并将对应的指针向前移动。
    • 重复上述步骤,直到两个链表中的一个为空。
    • 将非空链表的剩余部分直接连接到合并后的链表。
  1. 复杂度:时间复杂度O(nlogn),其中n是链表的长度;空间复杂度O(1)。
  2. c++ demo
#include <iostream>// 定义链表节点
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(NULL) {}
};class Solution {
public:ListNode* sortList(ListNode* head) {if (!head || !head->next) return head;// 找到链表的中点,准备分割链表ListNode* slow = head, * fast = head;while (fast->next && fast->next->next) {slow = slow->next;fast = fast->next->next;}// 切割链表ListNode* second = slow->next;slow->next = NULL;// 递归排序链表的两半ListNode* left = sortList(head);ListNode* right = sortList(second);// 合并排序后的链表return merge(left, right);}private:ListNode* merge(ListNode* l1, ListNode* l2) {// 合并两个有序链表ListNode dummy(0);ListNode* tail = &dummy;while (l1 && l2) {if (l1->val < l2->val) {tail->next = l1;l1 = l1->next;}else {tail->next = l2;l2 = l2->next;}tail = tail->next;}// 连接剩余部分tail->next = l1 ? l1 : l2;return dummy.next;}
};int main() {Solution solution;// 创建示例链表 4 -> 1 -> 3 -> 2 -> NULLListNode* head = new ListNode(4);head->next = new ListNode(1);head->next->next = new ListNode(3);head->next->next->next = new ListNode(2);// 排序链表ListNode* sortedHead = solution.sortList(head);// 打印排序后的链表for (ListNode* node = sortedHead; node; node = node->next) {std::cout << node->val << " -> ";}std::cout << "NULL" << std::endl;// 释放链表内存while (sortedHead) {ListNode* temp = sortedHead;sortedHead = sortedHead->next;delete temp;}return 0;
}
  • 输出结果:

1 -> 2 -> 3 -> 4 -> NULL
在这里插入图片描述

归并排序

归并排序(Merge Sort)是一种分治算法,用于对数组或列表进行排序。它基于以下两个原则:

  • 分解(Divide):将数组分成两半,直到每个子数组只有一个元素。
  • 合并(Conquer):将有序的子数组合并成更大的有序数组。

这篇关于LeetCode 算法:排序链表 c++的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1085762

相关文章

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

从入门到精通C++11 <chrono> 库特性

《从入门到精通C++11<chrono>库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段(Durat

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多,因为它实际属于c++20最为重要的

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》:本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识:传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决

C++11委托构造函数和继承构造函数的实现

《C++11委托构造函数和继承构造函数的实现》C++引入了委托构造函数和继承构造函数这两个重要的特性,本文主要介绍了C++11委托构造函数和继承构造函数的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、委托构造函数1.1 委托构造函数的定义与作用1.2 委托构造函数的语法1.3 委托构造函