92. 反转链表 II(C++)
2022/3/9 22:15:00
本文主要是介绍92. 反转链表 II(C++),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 题目
- 题解
题目
给你单链表的头指针 head
和两个整数 left
和 right
,其中 left
<= right
。请你反转从位置 left
到位置 right
的链表节点,返回 反转后的链表 。
示例 1:
输入:head = [1,2,3,4,5], left = 2, right = 4 输出:[1,4,3,2,5]
示例 2:
输入:head = [5], left = 1, right = 1 输出:[5]
提示:
- 链表中节点数目为 n
- 1 <= n <= 500
- -500 <= Node.val <= 500
题解
对于链表的问题,一般都是要建一个 dummy node
连上原链表的头结点,以此来规范头节点变动和其他节点变动的代码,进行格式统一。
以题目中的例子来说,变换的是 2,3,4 这三个点,我们需要找到第一个开始变换结点的前一个结点,只要让 pre 向后走 m-1 步即可,用 pre 指向它。由于一次只能交换两个结点,所以我们按如下的交换顺序:
1 -> 2 -> 3 -> 4 -> 5 -> NULL 1 -> 3 -> 2 -> 4 -> 5 -> NULL // 第一次变换将结点 3 放到结点 1 的后面 1 -> 4 -> 3 -> 2 -> 5 -> NULL // 第二次变换将结点 4 放到结点 1 的后面
可以看出来,总共需要 right-left
步即可,因为每次变换都是规律的操作,就以第一次变换进行举例。刚开始,pre
指向结点 1,cur
指向结点 2,然后我们建立一个临时的结点 tmp
,用临时变量保存某个结点就是为了首先断开该结点和前面结点之间的联系,这可以当作一个规律记下来。
每一次节点交换分为以下三个步骤:
-
第一步断开结点 2 和结点 3,将结点 2 的 next 连到结点 4 上:
cur->next = t->next
-
第二步将结点 3 连到结点2的前面,即
t->next = pre->next
-
第三步将结点 1 连到结点 3,即
pre->next = tmp
这里跟常见的链表反转最大的区别在于以前prev、cur会向随着链表遍历反转逐渐向后移动,这里的prev、cur其实指向并没有改变。即这里的prev一直是1, cur一直是2, 是cur->next一直在变化。
完整代码如下:
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseBetween(ListNode* head, int left, int right) { // 设置头节点,来规范化头节点反转的特殊情况 ListNode* dummy = new ListNode(-1); dummy->next = head; ListNode* pre = dummy; // left-1是为了找到开始变换节点的前一节点 for (int i = 0; i < left - 1; i++) pre = pre->next; // 本题中pre和cur不会变动!! ListNode* cur = pre->next; for (int i = left ; i < right; i++) { ListNode* tmp = cur->next; // 首先断开临时节点和前面节点的关系 cur->next = tmp->next; tmp->next = pre->next; pre->next = tmp; } return dummy->next; } };
这篇关于92. 反转链表 II(C++)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验