本文主要是介绍反转链表 II 简单链表问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
给你单链表的头指针 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]
在需要反转的区间里,每遍历到一个节点,让这个新节点来到反转部分的起始位置。下面的图展示了整个流程。
先将 curr 的下一个节点记录为 next;
执行操作 ①:把 curr 的下一个节点指向 next 的下一个节点;
执行操作 ②:把 next 的下一个节点指向 pre 的下一个节点;
执行操作 ③:把 pre 的下一个节点指向 next。
class Solution {
public:ListNode* reverseBetween(ListNode* head, int left, int right) { // 设置 dummyNode 是这一类问题的一般做法ListNode *dummyNode = new ListNode(-1);dummyNode->next = head;ListNode *pre = dummyNode;for (int i = 0; i < left - 1; i++) {pre = pre->next;}ListNode *cur = pre->next;ListNode *next;for (int i = 0; i < right - left; i++) {next = cur->next;cur->next = next->next;next->next = pre->next;pre->next = next;}return dummyNode->next;}
};
这篇关于反转链表 II 简单链表问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!