leetcode92 反转链表2
题目介绍：
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left curr_node -> next_node
反转后的状态： pre_node next;
cur->next=next->next;
next->next=pre->next;
pre->next=next;
这四步的顺序。
步骤
首先，我们创建一个名为 dummyNode 的 ListNode，将其值设为 -1，dummyNode.next 指向原始链表头节点 head，然后定义一个指针 pre 指向 dummyNode，用于找到要翻转的起点 left 前一个节点。设置起点 cur 为 pre.next。
然后，我们需要将第 left到第right个节点顺序翻转。我们使用一个循环，将 cur 节点后面的节点移动到它前面来，将其插入到 pre 节点的后面，如下：
- 首先，定义一个指针 next，让其指向 cur 的下一个节点，备份一下 cur 的下一个节点，方便后面使用。
- 然后更新 cur 节点的 next，使其指向 next 节点的 next。
- 接着，让 next 节点的 next 指向 pre 的下一个节点，将 next 节点插入到 pre 节点和 cur 节点之间。
- 最后，更新 pre 指针和 cur 指针，将它们指向下一个待翻转的节点位置。
反复执行循环，每次移动 cur 节点后面的节点，在 pre 节点和 cur 节点之间插入，直到将第 left 到第 right 个节点全部翻转完毕。函数执行完后，我们返回翻转后的链表头节点即 dummyNode.next。
为什么要使用虚拟头结点？
这里使用虚拟头结点的原因是因为可能翻转的区间是从头开始，那么可能就需要换头，而使用虚拟节点就可以不换头了。
代码
cpp代码如下：
/**
* 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;
for(int i=0;inext;
}
ListNode *cur=pre->next;
ListNode *next;
for(int i=0;inext;
cur->next=next->next;
next->next=pre->next;
pre->next=next;
}
return dummy->next;
}
};
java代码如下：
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;
}
思考
- 为什么 i < left - 1 ？
这个循环的目的是将 pre 指针移动到需要反转的起始位置之前的节点。因为 pre 最初指向 dummyNode 的头节点，所以我们需要移动 left - 1 次才能到达目标位置。
- 为什么 i < right - left ？
这个循环的目的是进行链表的反转操作。我们需要将从起始位置到终止位置的一段链表进行反转。因为我们已经移动了 left-1 步，所以这里我们只需反转 right - left 次。
- 为什么是ListNode *cur=pre->next;而非ListNode *cur=pre;？
因为在反转链表的过程中，我们需要将 cur 作为当前节点，然后将 next 作为下一个节点，并进行指针的调整。所以我们需要让 cur 指向 pre 的下一个节点，即 pre->next。这样才能保证链表可以正确地反转。
如果我们让 cur 等于 pre，那么实际上就是没有移动到下一个节点，而是一直停留在当前节点，导致链表无法反转。
方法二：双指针法（也可称为穿针引线法）
穿针引线的来历：先确定好需要反转的部分，也就是left 到 right 之间，然后再将三段链表拼接起来。这种方式类似裁缝一样，找准位置减下来，再缝回去。故形象地称之为穿针引线。
这种方法较之第一种实现难度较高，但复用性强。
步骤
画个图方便理解：
总结：将链表划分成三部分，先将待反转的区域反转，然后将反转的链表与原链表连接起来。
代码
以下是cpp代码：
/**
* 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;
for(int i=0;inext;
}
ListNode *leftNode=pre->next;
ListNode *rightNode=pre;
for(int i=0;inext;
}
ListNode *succ=rightNode->next;
rightNode->next=nullptr;
reverseList(leftNode);
pre->next=rightNode;
leftNode->next=succ;
return dummy->next;
}
ListNode* reverseList(ListNode* head) {
ListNode *currNode=head,*preNode=nullptr;
while(currNode!=nullptr){
ListNode *next=currNode->next;
currNode->next=preNode;
preNode=currNode;
currNode=next;
}
return preNode;
}
};
如果把leftNode->next=succ;反过来，写成succ=leftNode->next;则会报错。
错误代码为：runtime error: member access within null pointer of type 'ListNode' (solution.cpp)
错误原因为：试图使用空指针
在写代码时，要尽量避免该情况的出现，仔细检查时表示把空指针赋给了某个值。
以下是Java代码：
public ListNode reverseBetween(ListNode head, int left, int right) {
// 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论，在这一点上，方法一和方法二一样
ListNode dummyNode = new ListNode(-1);//定义一个虚拟结点
dummyNode.next = head;
ListNode pre = dummyNode;//pre为前驱
// step1:从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
//写在 for 循环里，可以使语义清晰
for (int i = 0; i < left - 1; i++) {
pre = pre.next;
}
// step2:从 pre 再走 right - left + 1 步，来到 right 节点
ListNode rightNode = pre;
for (int i = 0; i < right - left + 1; i++) {
rightNode = rightNode.next;
}
// step3:切出一个子链表
ListNode leftNode = pre.next;
ListNode succ = rightNode.next;//succ为后继
rightNode.next = null;
// step4：同第 206 题，反转链表的子区间
reverseLinkedList(leftNode);
// step5：接回到原来的链表中
pre.next = rightNode;
leftNode.next = succ;
return dummyNode.next;
}
private void reverseLinkedList(ListNode head) {
// 反转链表；也可以使用递归法反转
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
}
思考
- 如果rightNode.next = null;这里不设置next为null会怎么样？
如果没有 rightNode->next=nullptr; 则会导致整个链表没有断开，那么链表会成为一个环形，即从第 right+1 个结点到第 left-1 个结点会变成一个环，这样程序就会进入一个死循环并最终崩溃。
所以 rightNode->next=nullptr; 的作用是将第 right 个结点的 next 设为空指针，使得整个链表变成了两个子链表，从头节点到 left-1 个结点一个，从left个结点到 right 个结点一个，从 right+1 个结点以后的再一个。
- pre.next = rightNode;这里为什么可以用rightNode
在代码中，我们需要将左边界节点的前一个节点（即pre）的next指针指向右边界节点(rightNode)。而rightNode是在遍历到右边界节点的前一个节点时获得的，所以可以直接使用rightNode来指代右边界节点。也就是说，pre->next=rightNode这一步的作用是将左边界节点的前一个节点的next指针指向右边界节点。
- 为什么要让leftNode.next = succ;
在给定的代码中，leftNode表示要反转部分的起始节点，succ表示要反转部分的末尾节点的下一个节点。leftNode->next=succ;的目的是将反转后的部分与剩余部分连接起来，使整个链表保持完整。通过将leftNode的next指针指向succ，即将要反转部分的末尾节点的下一个节点，将反转后的部分的末尾节点与剩余部分连接起来，实现链表的拼接。
方法总结
反转指定区间链表可以使用以下四种方法：
- 头插法是一种利用辅助节点将每个节点插入到链表头部的方法。具体来说，我们先创建一个辅助节点，然后依次遍历链表中的每个节点，将其插入到辅助节点的后面，随后将辅助节点指向该节点。最后，我们将辅助节点后面的节点全部取出来，即为反转后的链表。
- 该方法的时间复杂度为O(n)，空间复杂度为O(1)。
- 这种方法思路简单，代码实现也直接。
- 以链表的指针作为遍历的方式，依次反转指定区间内的节点。每遍历到一个节点就将其反转，直到遍历完指定区间内的所有节点。具体来说，我们需要用三个指针，分别指向当前节点、前一个节点和后一个节点。每遍历一个节点，就将当前节点的指针指向前一个节点，并将当前节点的指针移动到后一个节点，直到遍历完整个链表为止。
- 该方法的时间复杂度为O(n)，空间复杂度为O(1)。
- 迭代法将原链表的节点一个个取下来再插入到新链表中，需要定义新链表和指向当前节点的指针，操作比较繁琐；而头插法通过在原链表头节点前插入一个虚拟节点，避免了对新链表的定义，并且只需要一个指向虚拟节点的指针，操作简单直观。
- 将指定区间内的节点分为两部分，第一部分是需要反转的，第二部分是不需要反转的。先递归反转第二部分，再反转第一部分，并将第一部分的尾节点连接到后面反转后的头节点。具体来说，我们调用一个函数，该函数会先递归到链表的最后一个节点，然后依次将每个节点的指针指向前一个节点，从而实现整个链表的反转。
- 该方法的时间复杂度为O(n)，空间复杂度为O(n)。
- 这种方法使用递归实现，相对来说比较难以理解。
- 使用两个指针 start 和 end 分别指向需要反转的区间的开始节点和结束节点，同时使用一个指针 prev 保存 start 前面的节点，使用一个指针 succ保存 end 后面的节点。然后将这个区间中的节点依次反转，直到反转到 end 节点位置。最后将反转的链表与原链表连接起来即可。
- 该方法的时间复杂度为O(n)，空间复杂度为O(1)。
- 这种方法思路清晰，易于理解。
欢迎关注我喵～持续更新ing
