92. 反转链表 II【150】（链表内指定区间反转）

左手的ㄟ右手 2023-09-23 15:48 112阅读 0赞

> **难度等级：中等**

> **上一篇算法：**
> 
> [剑指 Offer II 026. 重排链表【链表】][Offer II 026.]

> **力扣此题地址：**
> 
> [92. 反转链表 II - 力扣（LeetCode）][92. _ II - _LeetCode]

## 1.题目：链表内指定区间反转 ##

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表 。

![71393a8e70ef49c3b1d06bb63b4f6793.png][]

## 2.解题思路： ##

> 此题一共设置四个指针：
> 
> 指向链表第一个结点的头结点dummynode； 指向left前一个结点的pre；
> 
> 指向left结点的cur； 指向left下一个结点的next；
> 
> 分别把他们的位置初始化好，然后开始用while循环进行重定义指针的指向。把需要反转的区间的结点进行反转，每反转一个节点，需要调整三个指针的指向。
> 
> 因为链表没有索引位置，所以不能一步到位到目标结点位置，所以初始化pre指针的时候只能用for循环来遍历移动到目标位置。
> 
> **详细过程参考方法二：**
> 
> [反转链表 II - 反转链表 II - 力扣（LeetCode）][II - _ II - _LeetCode]

## 3.代码实现： ##

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode reverseBetween(ListNode head, int left, int right) {
            // 设置 dummyNode 是这一类问题的一般做法
            ListNode dummyNode = new ListNode(-1,null);
            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;//next要放在循环里，因为next在不断地向后移动
                cur.next = next.next;
                next.next = pre.next;
                pre.next = next;
            }
            return dummyNode.next;
        }
    }

[Offer II 026.]: https://blog.csdn.net/m0_51697147/article/details/127946678?spm=1001.2014.3001.5501
[92. _ II - _LeetCode]: https://leetcode.cn/problems/reverse-linked-list-ii/
[71393a8e70ef49c3b1d06bb63b4f6793.png]: https://img-blog.csdnimg.cn/71393a8e70ef49c3b1d06bb63b4f6793.png
[II - _ II - _LeetCode]: https://leetcode.cn/problems/reverse-linked-list-ii/solution/fan-zhuan-lian-biao-ii-by-leetcode-solut-teyq/