【3.18】LeetCode每日一题· 反转链表 II

2021年03月18日 11时07分

标签： LeetCode 链表

## 题目描述
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

#### 示例1
	输入: 1->2->3->4->5->NULL, m = 2, n = 4
	输出: 1->4->3->2->5->NULL

#### 提示
	1 ≤ m ≤ n ≤ 链表长度

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/reverse-linked-list-ii/ "题目链接")

## 解题思路
如果使用两趟扫描的话，可以首先遍历链表，找到需要反转的区间的头指针、头指针的前一个指针；尾指针、尾指针的后一个指针，然后将头尾指针之间的链表翻转后，再将头指针的前一个指针指向翻转链表的头指针（原来的尾指针），将翻转链表的尾指针（原来的头指针）指向尾指针的后一个指针即可。
对于区间翻转操作，需要对链表进行第二次遍历。在当前结点`cur`时，需要将其指向其前一个节点`prev`(当`cur`为头结点时，`prev`为`nullptr`)。由于指向前一个结点后，就无法访问原来该结点的后一个结了，因此需要先把该结点原来的后一个结点保存下来。
![3.18题解.svg](https://pic.stackoverflow.wiki/uploadImages/157/0/72/117/2021/03/18/11/04/66c0cfde-7ace-4ffb-9612-b7a58138a436.svg)

但是，方法一需要遍历链表两次，当left和right之间的区域很大时，速度较慢。我们可以对链表仅遍历一次实现。这里LeetCode的官方题解讲的比较清楚，就直接贴上来了。
我们依然以方法一的示例为例进行说明。
![](https://pic.leetcode-cn.com/1615105232-cvTINs-image.png)
整体思想是：在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。下面的图展示了整个流程。
![](https://pic.leetcode-cn.com/1615105242-ZHlvOn-image.png)

下面我们具体解释如何实现。使用三个指针变量 pre、curr、next 来记录反转的过程中需要的变量，它们的意义如下：
	
	curr：指向待反转区域的第一个节点 left；
	next：永远指向 curr 的下一个节点，循环过程中，curr 变化以后 next 会变化；
	pre：永远指向待反转区域的第一个节点 left 的前一个节点，在循环过程中不变。

第 1 步，我们使用 ①、②、③ 标注「穿针引线」的步骤。
![](https://pic.leetcode-cn.com/1615105296-bmiPxl-image.png)
操作步骤：
	
	先将 curr 的下一个节点记录为 next；
	执行操作 ①：把 curr 的下一个节点指向 next 的下一个节点；
	执行操作 ②：把 next 的下一个节点指向 pre 的下一个节点；
	执行操作 ③：把 pre 的下一个节点指向 next。
第 1 步完成以后「拉直」的效果如下：
![](https://pic.leetcode-cn.com/1615105340-UBnTBZ-image.png)
第 2 步，同理。同样需要注意 「穿针引线」操作的先后顺序。
![](https://pic.leetcode-cn.com/1615105353-PsCmzb-image.png)
第 2 步完成以后「拉直」的效果如下：
![](https://pic.leetcode-cn.com/1615105364-aDIFqy-image.png)
第 3 步，同理。
![](https://pic.leetcode-cn.com/1615105376-jIyGwv-image.png)
第 3 步完成以后「拉直」的效果如下：
![](https://pic.leetcode-cn.com/1615105395-EJQnMe-image.png)
> 作者：LeetCode-Solution
> 链接：[https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/fan-zhuan-lian-biao-ii-by-leetcode-solut-teyq/](#)
> 来源：力扣（LeetCode）
> 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

## 代码
```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 *h = new ListNode(0);
        h->next = head;
        ListNode *p = h;
        int cnt = 0;
        while(cnt < left-1){
            p=p->next;
            cnt++;
        }
        ListNode *beforeFirst = p;
        p = p->next;
        while(cnt < right-1){
            ListNode *cur = p, *proc = p->next;
            cur->next = proc->next;
            proc->next = beforeFirst->next;
            beforeFirst->next = proc;
            cnt++;
        }
        return h->next;
    }
};
```

### 用时和内存
> 执行用时：0 ms，在所有 C\++提交中击败了100.00%的用户
> 内存消耗：7.2 MB，在所有 C\++提交中击败了61.29%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.18】LeetCode每日一题· 反转链表 II

所有评论

暂无评论

新增评论