LeetCode 算法:K 个一组翻转链表 c++

2024-06-21 07:04

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

原题链接🔗:K 个一组翻转链表
难度:困难⭐️⭐️⭐️

题目

给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。

k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

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

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

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

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

提示

  • 链表中的节点数目为 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

进阶:你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗?

题解

迭代法

  1. 题解

"K 个一组翻转链表"是LeetCode上的一道中等难度的题目,其解题思路可以概括如下:

  1. 理解问题:题目要求将给定的链表按照每K个节点为一组进行翻转,如果最后一组不足K个节点,则不翻转。

  2. 使用哑节点:在链表的头部添加一个哑节点(dummy node),这样无论原链表的头节点如何变化,哑节点始终作为链表的起始点,简化了边界条件的处理。

  3. 遍历链表:从头节点开始遍历链表,找到每K个节点的边界。

  4. 翻转每组节点:对于每组找到的K个节点,进行翻转操作。翻转操作可以通过迭代或递归实现。

  5. 连接翻转后的节点:将翻转后的节点连接到前一组翻转后的节点后面,形成新的链表。

  6. 递归与迭代:递归方法简洁但可能存在栈溢出的风险,迭代方法更安全但代码相对复杂。

  7. 边界条件处理:处理链表长度不足K的情况,以及翻转后的链表连接。

下面详细说明迭代方法的步骤:

迭代方法

  1. 初始化:使用哑节点指向头节点,定义两个指针groupPrevcurr,分别指向当前组的前一个节点和当前处理的节点。

  2. 找到每K个节点:使用curr指针遍历链表,找到每K个节点的最后一位,可以通过一个循环实现。

  3. 翻转操作:在找到每K个节点后,使用三个指针(prevcurrentnext)来翻转这K个节点的连接。

  4. 连接翻转后的节点:将翻转后的节点连接到groupPrev后面。

  5. 更新指针:更新groupPrev为当前翻转组的最后一个节点,curr为下一个未翻转的节点的开始。

  6. 循环:重复步骤2-5,直到currnullptr,表示链表已经完全遍历。

  7. 返回结果:返回哑节点的下一个节点,即翻转后的链表的头节点。

递归方法

递归方法的核心是将问题分解为更小的子问题:

  1. 定义递归函数:递归函数接收当前节点和K值。

  2. 终止条件:如果当前节点为空或K为1,直接返回当前节点。

  3. 找到K个节点:使用辅助函数找到第K个节点。

  4. 翻转操作:翻转当前节点到第K个节点之间的链表。

  5. 递归调用:对第K个节点之后的链表进行递归调用。

  6. 连接翻转后的节点:将翻转后的子链表连接到翻转前的子链表。

  7. 返回结果:返回翻转后的链表。

递归方法的关键在于正确地翻转子链表,并确保递归调用能够正确地处理剩余的链表部分。递归方法的代码实现通常更简洁,但需要注意递归深度和性能问题。

  1. 复杂度:时间复杂度O(n),空间复杂度O(1)。
  2. c++ demo:直接应用LeetCode C++10-K个一组翻转链表中的demo。
#include <iostream>
#include <memory> //std::shared_ptr
#include <utility> // std::pairstruct Node {int value;Node* next;Node(int value) {this->value = value;next = nullptr; //这个千万别忘了,否则容易引发segment fault}
};Node* reverse(Node* head) {Node* pre = nullptr;Node* p = head;while (p) {auto next = p->next;p->next = pre;pre = p;p = next;}return pre;
}// 翻转[head, tail]的元素
std::pair<Node*, Node*> reverse(Node* head, Node* tail) {if (head == nullptr || tail == nullptr) {return {};}Node* pre = nullptr;Node* p = head;// 特别注意:// 这里容易错写成while(p != tail->next),显然是错误的.// 原因是tail对应的元素翻转后,tail->next不再指向原来的next,而是指向翻转后的next// 除非提前将tail->next在循环外保存,例如:// Node* tail_next = tail->next;// while (p != tail_next) {...}while (pre != tail) { // 这里容易错写成p != tail->nextNode* next = p->next;p->next = pre;pre = p;p = next;}return { tail, head };
}Node* reverse_k(Node* head, int k) {std::shared_ptr<Node> dummy_node(new Node(-1));dummy_node->next = head;Node* pre = dummy_node.get();Node* phead = head;Node* ptail = pre;//从真正头节点前一个位置出发while (phead) {for (int i = 0; i < k; i++) {ptail = ptail->next;if (ptail == nullptr) { //长度不够k则直接返回return dummy_node->next;}}Node* next = ptail->next;//先保存tail的下一个位置,防止断链auto reverse_ret = reverse(phead, ptail);//翻转[phead, ptail]区间phead = reverse_ret.first;ptail = reverse_ret.second;// 更新连接pre->next = phead;ptail->next = next;// 指针向前移动pre = ptail;phead = next;}return dummy_node->next;
}void print_list(Node* head) {Node* p = head;while (p) {std::cout << p->value << "->";p = p->next;}std::cout << "nullptr" << std::endl;;
}int main()
{// case1: 1->2->3->4->5, k=2 ==> 2->1->4->3->5Node n1(1), n2(2), n3(3), n4(4), n5(5);n1.next = &n2;n2.next = &n3;n3.next = &n4;n4.next = &n5;Node* head = &n1;print_list(head);head = reverse_k(head, 2);std::cout << "case1, k=2:" << std::endl;print_list(head);// case2: 1->2->3->4->5, k=3 ==> 3->2->1->4->5n1.next = &n2;n2.next = &n3;n3.next = &n4;n4.next = &n5;head = &n1;head = reverse_k(head, 3);std::cout << "case2, k=3:" << std::endl;print_list(head);// case3: 1->2->3->4->5, k=1 ==> 1->2->3->4->5n1.next = &n2;n2.next = &n3;n3.next = &n4;n4.next = &n5;head = &n1;head = reverse_k(head, 1);std::cout << "case3, k=1:" << std::endl;print_list(head);// case4: 1, k = 1 n1.next = nullptr;head = &n1;head = reverse_k(head, 1);std::cout << "case3, list is 1->nullptr, k=1:" << std::endl;print_list(head);return 0;
}
  • 输出结果:

1->2->3->4->5->nullptr
case1, k=2:
2->1->4->3->5->nullptr
case2, k=3:
3->2->1->4->5->nullptr
case3, k=1:
1->2->3->4->5->nullptr
case3, list is 1->nullptr, k=1:
1->nullptr
在这里插入图片描述

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



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

相关文章

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 委托构造函

C++11作用域枚举(Scoped Enums)的实现示例

《C++11作用域枚举(ScopedEnums)的实现示例》枚举类型是一种非常实用的工具,C++11标准引入了作用域枚举,也称为强类型枚举,本文主要介绍了C++11作用域枚举(ScopedEnums... 目录一、引言二、传统枚举类型的局限性2.1 命名空间污染2.2 整型提升问题2.3 类型转换问题三、C

C++链表的虚拟头节点实现细节及注意事项

《C++链表的虚拟头节点实现细节及注意事项》虚拟头节点是链表操作中极为实用的设计技巧,它通过在链表真实头部前添加一个特殊节点,有效简化边界条件处理,:本文主要介绍C++链表的虚拟头节点实现细节及注... 目录C++链表虚拟头节点(Dummy Head)一、虚拟头节点的本质与核心作用1. 定义2. 核心价值二

C++ 检测文件大小和文件传输的方法示例详解

《C++检测文件大小和文件传输的方法示例详解》文章介绍了在C/C++中获取文件大小的三种方法,推荐使用stat()函数,并详细说明了如何设计一次性发送压缩包的结构体及传输流程,包含CRC校验和自动解... 目录检测文件的大小✅ 方法一:使用 stat() 函数(推荐)✅ 用法示例:✅ 方法二:使用 fsee