牛客TOP101：链表内指定区间反转

1. 题目描述

2. 解题思路

  在做这道题之前希望大家先把链表翻转这个题写一下。
  这道题和反转链表的区别在于：它仅仅只翻转其中的某一个区间，但是我们可以将问题进行转化，转化为翻转链表。
  我们可以将翻转区间之外的部分先忽略掉，这样问题就转化为了翻转整个链表。在翻转完成后，在将剩余的部分连接起来就可以了。
  在连接时需要注意： 如果翻转的区间包含了头节点，那么翻转之后的函数返回值就不再时原来的头节点了，而是我们翻转之后的结点（做过翻转链表这个题就知道为什么了），如果翻转区间不包含头节点，那么最终的返回值依旧是原来的头节点。（因此这里是需要进行判断的）
  我在代码实现部分详细说明的每一步的代码意义，相信会对大家有所帮助。

3. 代码实现

/**
 * struct ListNode {
 *int val;
 *struct ListNode *next;
 *ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
    // 如果链表为空或者翻转区间只有一个结点，直接返回
        if(head == nullptr || (m == n)) return head;

// left结点的意义：翻转区间的第一个结点
// right结点的意义： 翻转区间的最后一个结点
// begin结点的意义： 翻转区间前的结点
        ListNode *left = head, *right = head, *begin = nullptr;
        // 找到left
        for(int i = 1; i < m; i++)
        {
        // 重点：如果翻转区间从1开始，也就是包含了头节点
        //      那么这个循环就不会进去
        //      那么begin的值就是nullptr —— 会方便后续的判断
            begin = left;  
            left = left->next;
        }
        // 找到right
        for(int i = 1; i < n; i++)
        {
            right = right->next;
        }

// tail结点的意义：翻转区间后面的结点
        ListNode* tail = right->next;

// 标记第一个进行翻转的结点（与链表翻转一题的写法一致）
        ListNode* cur = left, *prev = begin, *next = cur->next;

        int num = n - m + 1;  // 需要翻转的结点数
        // while(num--)
        for(int i = 1; i <= num; i++)
        {
            cur->next = prev;
            prev = cur;
            cur = next;
            if(next)
                next = next->next;
        }

        // 如果翻转的范围不包括头节点，那么就进行连接
        if(begin != nullptr)
        {
            begin->next = right;
            left->next = tail;
            return head;
        }

        // 到这里说明翻转的范围包括了头节点，那么就意味这返回的结点不再是原来的头节点了，返回的是翻转完成之后的结点
        // 同时需要考虑尾部是否还有结点
        if(tail != nullptr)
        {
            left->next = tail;        
        }
        return prev;
    }
};

原文地址：https://blog.csdn.net/qq_62321047/article/details/140451475

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！