【算法】链表：92.反转链表（medium）+双指针

 系列专栏

《分治》

《模拟》

《Linux》

---

目录

1、题目链接 

2、题目介绍

3、解法 （双指针）

4、代码

---

是 206. 反转链表 - 力扣（LeetCode）的类型题，且难度提升，可以先完成206，然后参照206的思路，解决本题。

1、题目链接 

 92. 反转链表 II - 力扣（LeetCode）

2、题目介绍

​

3、解法 （双指针）

1. 创建虚拟节点：
   • 为了简化边界情况的处理，尤其是当left为1时，即需要翻转的链表部分从头节点开始，此时我们难以直接操作头节点。因此，我们创建一个虚拟节点dummy，其next指向原链表的头节点head。这样，我们总可以操作dummy->next而无需担心修改原始头节点。
   • 
2. 定位left位置的前一个节点：
   • 我们需要遍历链表直到left-1的位置，以便找到left位置节点的前一个节点。这个节点在后续翻转过程中将作为新链表的尾部节点（因为它后面接的是需要翻转的部分），并且在翻转完成后，它将指向翻转后部分的新头节点。
   • 变量cur用于遍历链表，直到它指向left位置的前一个节点。
   • 终止位置是left-1。
   • 
3. 准备翻转：
   • pre指向left位置的节点，这是翻转部分的起始节点。
   • lLEFT存储left位置前一个节点的引用，这样在翻转后，我们可以将其与翻转后的链表部分重新链接。
4. 执行翻转：
   • 我们需要翻转从left到right的节点。
   • 使用三个指针pre（当前节点的前一个节点），pre->next（当前节点），和tmp（当前节点的下一个节点）。
   • 翻转操作通过改变节点间的next指针来实现：将当前节点的next指向它的前一个节点pre，然后移动pre和cur指针到下一个节点。
   • 循环继续直到cur到达right位置的节点。此时，pre指向right位置的下一个节点，而cur指向right位置的节点。
5. 重新链接：
   • 翻转完成后，我们需要将翻转后的部分与链表的其他部分重新链接。
   • lLEFT->next->next指向right位置之后的节点（即pre），这是因为lLEFT->next现在是翻转部分的新头节点（原right位置的节点），而我们需要将它的next指向翻转部分之后的节点。
   • lLEFT->next指向翻转部分的新头节点（即原right位置的节点，现在的cur）。
6. 返回结果：
   • 虚拟节点dummy的next指向原始链表的头节点或翻转后的新头节点（如果翻转从头部开始）。因此，返回dummy->next即可得到最终翻转后的链表。

4、代码

/*** 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(0);//虚拟结点dummy->next = head;ListNode* cur= dummy;//找到left位置的前一个结点for (int i = 0; i < left - 1; i++){cur = cur->next;}ListNode* pre = cur->next;ListNode* lLEFT= cur;//用来存储left位置的前一个结点//翻转区域//保存头尾结点，方便之后和其他区域链接for (int i = left - 1; i < right; i++){ListNode* tmp = pre->next;pre->next = cur;cur = pre;//cur最后会是right对应的结点pre = tmp;//PRE最后会是right的下一个结点}//链接翻转区域lLEFT->next->next = pre;lLEFT->next = cur;return dummy->next;}
};

---

💗感谢阅读！💗

---