算法通关村第二关——指定区间反转的问题解析

野性酷女 2024-03-22 22:01 109阅读 0赞

### 题目类型 ###

> 指定区间反转

#### 题目描述 ####

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

#### 示例 ####

> 输入：head = \[1,2,3,4,5\] , left = 2 , right = 4
> 
> 输出：\[1,4,3,2,5\]

#### 图例 ####

![image.png][]

#### 解题方法 ####

> 1.头插法 ：带头节点的反转
> 
> 2. 穿针引线法：不带头节点的反转

##### 头插法 #####

###### 思想 ######

> 在需要反转的区间里，每遍历到一个节点（向后遍历），让这个新节点（后面的节点）来到反转部分的起始位置（left的位置）

###### 例 ######

下图中，蓝色部分是需要进行反转的位置，即 left = 3 ，right = 6

![image.png][image.png 1]

反转流程

![image.png][image.png 2]

###### 代码实现 ######

public Node reverseBetween(Node head, int left, int right){
        
        Node dummyNode = new Node(0);
        dummyNode.next = head;
        Node pre = dummyNode;
        for(int i = 0 ; i < left -1 ; i++){
            pre = pre.next;
        }
        Node cur = pre.next;
        Node 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;
    }

理解循环代码：

> 整个循环的大致逻辑 是 将cur后面的节点插入到pre的后面，然后将链接补好

带图理解

![23404ba596ae4ebc89323bc55608687a.png][]

带注释版代码

/**
         * 题目：
         * 给你单链表的头指针head和两个整数left和right，其中left <= right。请反转从位置left到位置right的链表节点，返回反转后的链表
         * 示例：
         * 输入：head = [1,2,3,4,5] ,left = 2 , right = 4
         * 输出：[1,4,3,2,5]
         *
         * 头插法（使用虚拟头节点）
         * @param head 链表头指针
         * @param left 左区间
         * @param right 右区间
         * @return 反转后的链表头节点
         */
        public Node reverseBetween(Node head , int left, int right){
            // 设置虚拟头节点
            Node dummyNode = new Node(0);
            // 将next指针指向头节点
            dummyNode.next = head;
            //  pre指针指向要操作节点的前一个位置
            Node pre = dummyNode;
            // 将pre指针走到left区间前的一个位置
            for (int i = 0; i < left - 1; i++) {
                pre = pre.next;
            }
            //  cur指针指向当前节点，要向后调整的节点（从  前---------->后）
            Node cur = pre.next;
            // next指针指向当前节点的下一个节点，即是 需要向前调整节点（从   后--->前）
            Node next;
            // 大致逻辑：将cur后面的插入到pre的后面，这样一个操作算1次
            for (int i = 0; i < right - left; i++) {
                // 将next指针指向当前节点的下一个节点
                next = cur.next;
                // 将next的下一个节点 作为 当前节点的下一个节点，即  向后移动
                cur.next = next.next;
                //  将next的下一个指针  指向  pre的后面，找到插入位置  ，即向前移动
                next.next = pre.next;
                //  将pre节点的下一个域 移动到 当前next节点上，即cur节点。表示当前一轮移动已经结束，准备下一轮的移动
                pre.next = next;
            }
            return dummyNode.next;
        }

##### 穿针引线法 #####

###### 实例 ######

如下图所示，蓝色部分是需要反转的区间，其反转前和反转后的效果如下：

![image.png][image.png 3]

##### 实现 #####

> 先确定好需要反转的部分，也就是下图的left和right之间，然后再将上端链表拼接起来。这种方式类似裁缝一样，找准位置，然后减下来，再缝回去。这样一来，就需要考虑如何标记下图的这四个位置了，以及如果反转left到right之间的链表。

![image.png][image.png 4]

##### 算法步骤 #####

> 1.先将待反转的区域反转（可以使用链表反转的方法实现）
> 
> 2. 把pre的next 指针指向反转以后的链表头节点，把反转以后的链表的尾节点的next指针指向succ(之前切下来剩余的后部分链表)

![image.png][image.png 5]

##### 注意点 #####

> 链接什么时候切断，什么时候补上去；这两个先后顺序需要想清楚。
> 
> 防止链表在反转后出现环形结构，需要在切完链表形成一个子链表后，将rightNode== null

##### 代码实现 #####

public Node reverseBetween(Node head, int left, int right){
    
        Node dummyNode = new Node(0,head);
        Node pre = dummyNode;
        
        for(int i = 0 ; i < left -1; i++){
            pre = pre.next;
        }
        Node rightNode = pre.next;
        for(int i = 0; i <= right-left; i++){
            rightNode = rightNode .next;
        }
        Node leftNode = pre.next;
        Node endNode = rightNode.next;
    
        rightNode = null;
        
        this.reverseList(leftNode);
    
        pre.next = rightNode;
        leftNode.next = endNode;
        
        return dummyNode;
    
    }
    private void reverseList(Node head){
        Node pre = null;
        Node cur = head;
        while(cur != null){
          Node next = cur.next;
          cur.next = pre;
          pre = cur;
          cur = next;
        }
    }

带注释代码实现

/**
         * 穿针引线法实现链表区间反转
         *
         * @param head  链表头节点
         * @param left  左区间位置
         * @param right 右区间位置
         * @return 新的链表节点
         */
        public Node reverseBetween1(Node head , int left ,int right){
            //定义虚拟节点
            Node dummy = new Node(0,head);
            Node pre = dummy;
            // 1. 从虚拟头节点走 left-1 步 ，来到left节点的前一个节点
            for (int i = 0; i < left - 1; i++) {
                pre = pre.next;
            }
            Node rightNode = pre;
            //2.从pre 再走 right-left+1 步，来到right节点
            for (int i = 0; i < right - left + 1; i++) {
                rightNode = rightNode.next;
            }
            //3 切出一个链表
            Node leftNode = pre.next;
            Node fail = rightNode.next;
            // 这一步的意义：防止链表在反转后出现环形结构
            // 如果不将rightNode.next设置为null，则rightNode的next指针可能仍然指向以前的节点，而不是指向区间反转后的新节点
            // 断开了rightNode与fail的连接，形成了新的链表，确保了链表的完整性
            rightNode.next = null;
    
            // 4. 反转链表子区间
            this.reverseList(leftNode);
    
            // 5. 接回到原来的链表汇总
            pre.next = rightNode;
            leftNode.next = fail;
    
            return dummy.next;
        }
    
        private void reverseList(Node head){
            Node pre = null;
            Node cur = head;
            Node next;
            while (cur != null){
                 next = cur.next;
                 cur.next = pre;
                 pre =cur;
                 cur = next;
            }
        }

######  ######

[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/5b131824c3504ed58180aae6600587a6.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/2d9faead32fc4d95b70f982927735d53.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/daf21c9cd20f4528a6ddad94ee2392af.png
[23404ba596ae4ebc89323bc55608687a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/55fb1c1d353448b0a9dedf8a9a46a33f.png
[image.png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/cd296b80adfc493a9f69c44a39177239.png
[image.png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/27b9584e35c64fdeb78acc09d7b5aada.png
[image.png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/bd0d6bf2ea0b424eb00c3bbfbc063915.png