链表内指定区间反转

待我称王封你为后i 2022-12-04 01:25 131阅读 0赞

# 链表内指定区间反转 #

## 1、参考资料 ##

https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c

## 2、题目要求 ##

> **题目描述**

将一个链表 `m` 位置到 `n` 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度为 O(1)

例如：给出的链表是 `1 --> 2 --> 3 --> 4 --> 5 --> null`，`m = 2`，`n = 4`；返回的链表为 `1 --> 4 --> 3 --> 2 --> 5 --> null`

注意：给出的 `m`，`n` 满足如下条件：`1 <= m <= n <= 链表长度`

> **示例1**

输入

{1,2,3,4,5},2,4

输出

{1,4,3,2,5}

## 3、代码思路 ##

思路说明

1.  单链表的反转有这么一种做法：先定义一个 `dummyHead`，然后遍历链表中每一个节点 `curNode`，将当前遍历的节点添加到 `dummyHead` 之后，成为新的首节点，即 `curNode.next = dummyHead.next; dummyHead.next = curNode`，因为我们改变了当前节点的 `next` 节点，在遍历过程中，我们需要使用临时变量将 `curNode.next` 存储起来，否则无法找到 `curNode` 的下一个节点
2.  这道题我们就仿造着这样的思路来做，首先为整个链表添加一个 `dummyHead`，添加 `dummyHead` 的原因在后面的描述中可以体会到其用处
3.  我们定义两个指针：`front` 和 `rear`，`front` 在第 `m - 1` 个节点停住，目的是将 `front` 作为第 `m` 个节点的 `dummyHead`，用于反转操作；`rear` 一直往后移动，直到链表反转完成
4.  当 `front` 在第 `m - 1` 个节点停住时，我们开始进行反转操作，每次将 `rear` 指向的节点放在 `front` 之后，成为新的首节点，然后让 `rear` 后移即可，当 `rear` 走到第 `n` 个节点时，将第 `n` 个节点反转后，链表反转完成
5.  现在链表最后还剩下一些节点，此时 `rear` 指向这段子链表的首节点，我们需要将反转后链表的尾节点(`reverseRear`)指向 `rear` ，便大功告成，当 `front` 停在第 `m - 1` 个节点时，我们就需要记录此时 `rear` 指向的节点，因为该节点在反转后成功新链表的尾节点，即反转完成后执行 `reverseRear.next = rear`
6.  现在我们可以解释为什么要为整个链表添加一个 `dummyHead`，因为如果 `m = 1`，证明从链表的第一个节点开始反转，但是第一个节点并没有前驱节点，所以我们需要为链表添加一个头结点

--------------------

举例说明

1.  现有如下链表，此时 `m = 2`，`n = 4`
    
        1 --> 2 --> 3 --> 4 --> 5 --> null
2.  为链表添加一个 `dummyHead`，初始化 `front = dummyHead`，`rear = head`
    
        dummyHead --> 1 --> 2 --> 3 --> 4 --> 5 --> null
            ^         ^
            |         |
           front     rear
3.  将 `front` 移动至第 `m - 1` 个节点处，停住
    
        dummyHead --> 1 --> 2 --> 3 --> 4 --> 5 --> null
                      ^     ^
                      |     |
                    front  rear
4.  执行反转操作 `rear.next = front.next; front.next = rear;`，不好画图，自行脑补
    
        dummyHead --> 1 --> 2 --> 3 --> 4 --> 5 --> null
                      ^     ^
                      |     |
                    front  rear
5.  当执行完反转后后，链表结构如下，此时需要让 `reverseRear` 指向 `rear`，即 `reverseRear = rear`
    
        dummyHead --> 1 --> 4 --> 3 <--> 2       5 --> null
                      ^                  ^       ^
                      |                  |       | 
                    front           reverseRear rear
6.  执行完后，链表结构如下
    
        dummyHead --> 1 --> 4 --> 3 <--> 2 ----> 5 --> null
                      ^                  ^       ^
                      |                  |       | 
                    front           reverseRear rear

## 4、代码实现 ##

代码

class Solution {
        
        public ListNode reverseBetween(ListNode head, int m, int n) {
        
            // 为链表创建一个 DummyHead
            ListNode dummyHead = new ListNode(0);
            dummyHead.next = head;
    
            ListNode front = dummyHead; // 初始化时，front 指针指向 dummyHead
            ListNode rear = head; // 初始化时，rear 指针指向 head
            ListNode reverseRear = null; // 用于记录反转后链表的尾节点
    
            // 当 rear 指向第 n 个节点时，链表反转完毕
            for (int i = 1; i <= n; i++) {
        
                if (i >= m) {
        
                    // 当 front 在第 m - 1 个节点停住，执行反转操作
                    ListNode nextNode = rear.next;
                    rear.next = front.next;
                    front.next = rear;
                    rear = nextNode;
                } else {
        
                    // 还未到达第 m - 1 个节点，front 和 rear 后移
                    front = front.next;
                    rear = rear.next;
                }
                // 当 front 指向第  m - 1 个节点时，记录 rear，此时的 rear 是链表反转后的尾节点
                if (i == m) {
        
                    reverseRear = rear;
                }
            }
    
            // 将剩余的节点链上
            reverseRear.next = rear;
            // 返回链表首节点
            return dummyHead.next;
        }
    }
    
    class ListNode {
        
        int val;
        ListNode next = null;
    
        public ListNode(int val) {
        
            this.val = val;
        }
    }