【算法】链表：92.反转链表（medium）+双指针
系列专栏
《分治》
《模拟》
《Linux》
目录
1、题目链接
2、题目介绍
3、解法 （双指针）
4、代码
是 206. 反转链表 - 力扣（LeetCode）的类型题，且难度提升，可以先完成206，然后参照206的思路，解决本题。
1、题目链接
92. 反转链表 II - 力扣（LeetCode）
2、题目介绍
3、解法 （双指针）
- 创建虚拟节点：
- 为了简化边界情况的处理，尤其是当
left为1时，即需要翻转的链表部分从头节点开始，此时我们难以直接操作头节点。因此，我们创建一个虚拟节点dummy，其next指向原链表的头节点head。这样，我们总可以操作dummy->next而无需担心修改原始头节点。- 定位left位置的前一个节点：
- 我们需要遍历链表直到
left-1的位置，以便找到left位置节点的前一个节点。这个节点在后续翻转过程中将作为新链表的尾部节点（因为它后面接的是需要翻转的部分），并且在翻转完成后，它将指向翻转后部分的新头节点。- 变量
cur用于遍历链表，直到它指向left位置的前一个节点。- 终止位置是left-1。
- 准备翻转：
pre指向left位置的节点，这是翻转部分的起始节点。lLEFT存储left位置前一个节点的引用，这样在翻转后，我们可以将其与翻转后的链表部分重新链接。- 执行翻转：
- 我们需要翻转从
left到right的节点。- 使用三个指针
pre（当前节点的前一个节点），pre->next（当前节点），和tmp（当前节点的下一个节点）。- 翻转操作通过改变节点间的
next指针来实现：将当前节点的next指向它的前一个节点pre，然后移动pre和cur指针到下一个节点。- 循环继续直到
cur到达right位置的节点。此时，pre指向right位置的下一个节点，而cur指向right位置的节点。- 重新链接：
- 翻转完成后，我们需要将翻转后的部分与链表的其他部分重新链接。
lLEFT->next->next指向right位置之后的节点（即pre），这是因为lLEFT->next现在是翻转部分的新头节点（原right位置的节点），而我们需要将它的next指向翻转部分之后的节点。lLEFT->next指向翻转部分的新头节点（即原right位置的节点，现在的cur）。- 返回结果：
- 虚拟节点
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;
}
};