11111

BM2.链表内指定区间反转

https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=295&sfm=html&channel=nowcoder

题目的主要信息：

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转
链表其他部分不变，返回头节点

方法一：头插法迭代（推荐使用）

具体做法：

肯定是要先找到了第m个位置才能开始反转链表，而反转的部分就是从第m个位置到第n个位置。

step 1：我们可以在链表前加一个表头，后续返回时去掉就好了，因为如果要从链表头的位置反转，也很方便。
step 2：使用两个指针，一个指向当前节点，一个指向前序节点。
step 3：依次遍历链表，到第m个的位置。
step 4：对于从m到n这些个位置的节点，依次断掉指向后续的指针，反转指针方向。
step 5：返回时去掉我们添加的表头。

具体过程如下图所示：

alt

Java实现代码：

import java.util.*;
public class Solution {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        ListNode res = new ListNode(-1); //加个表头
        res.next = head;
        ListNode pre = res; //前序节点
        ListNode cur = head; //当前节点
        for(int i = 1; i < m; i++){ //找到m
            pre = cur;
            cur = cur.next;
        }
        for(int i = m; i < n; i++){ //从m反转到n
            ListNode temp = cur.next;
            cur.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        return res.next; //返回去掉表头
    }
}

C++实现代码：

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* res = new ListNode(-1); //加个表头
        res->next = head;
        ListNode* pre = res; //前序节点
        ListNode* cur = head; //当前节点
        for(int i = 1; i < m; i++){ //找到m
            pre = cur;
            cur = cur->next;
        }
        for(int i = m; i < n; i++){ //从m反转到n
            ListNode* temp = cur->next;
            cur->next = temp->next;
            temp->next = pre->next;
            pre->next = temp;
        }
        return res->next; //返回去掉表头
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，最坏情况下遍历全部链表
空间复杂度： $O (1)$ ，无额外空间使用

方法二：递归（扩展思路）

具体做法：

我们来看看另一种分析：如果m == 1，就相当于反转链表的前 $n$ 元素；如果 m != 1我们把 head 的索引视为 1，那么我们是想从第 $m$ 个元素开始反转，如果把 head.next 的索引视为1，那相对于 head.next的反转的区间应该是从第 $m - 1$ 个元素开始的，以此类推，反转区间的起点往后就是子问题，我们可以使用递归处理：

终止条件： 当m == 1，就可以直接反转前n个元素。
返回值： 将已经反转后的子问题头节点返回给上一级。
本级任务： 递归地缩短区间，进入子问题反转。

而每次反转，如果n == 1，相当于只颠倒第一个节点，如果不是，则进入后续节点（子问题），因此反转过程也可以使用递归：

终止条件： 当n == 1时，只反转当前头节点即可。
返回值： 将子问题反转后的节点头返回。
本级任务： 缩短 $n$ 进入子问题反转，并将当前节点接在反转后子问题的后面。

具体步骤如下：

step 1：按照第一个递归的思路缩短子问题找到反转区间的起点。
step 2：按照第二个递归的思路缩短终点的子问题，从第 $n$ 个位置开始反转，往上拼接。

Java实现代码：

import java.util.*;
public class Solution {
    ListNode temp = null;
    public ListNode reverse(ListNode head, int n){
        if(n == 1){ //只颠倒第一个节点，后续不管
            temp = head.next;
            return head;
        }
        ListNode node = reverse(head.next, n - 1); //进入子问题
        head.next.next = head; //反转
        head.next = temp; //拼接
        return node;
    }
    public ListNode reverseBetween (ListNode head, int m, int n) {
        if(m == 1) //从第一个节点开始
            return reverse(head, n);
        ListNode node = reverseBetween(head.next, m - 1, n - 1); //缩减子问题
        head.next = node; //拼接已翻转
        return head;
    }
}

C++实现代码：

class Solution {
public:
    ListNode* temp = NULL;
    ListNode* reverse(ListNode* head, int n){
        if(n == 1){ //只颠倒第一个节点，后续不管
            temp = head->next;
            return head;
        }
        ListNode* node = reverse(head->next, n - 1); //进入子问题
        head->next->next = head; //反转
        head->next = temp; //拼接
        return node;
    }
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(m == 1) //从第一个节点开始
            return reverse(head, n);
        ListNode* node = reverseBetween(head->next, m - 1, n - 1); //缩减子问题
        head->next = node; //拼接已翻转
        return head;
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，最坏情况下遍历全部链表
空间复杂度： $O (n)$ ，递归栈深度最坏为 $n$

alt alt

像这种子串长度的题，一般都涉及状态转移，可以用动态规划的方式。

step 1：用 $d p [i]$ 表示以下标为i的字符为结束点的最长合法括号长度。
step 2：很明显知道左括号不能做结尾，因此但是左括号都是 $d p [i] = 0$ 。
step 3：我们遍历字符串，因为第一位不管是左括号还是右括号dp数组都是0，因此跳过，后续只查看右括号的情况，右括号有两种情况：
- 情况一：
如图所示，左括号隔壁是右括号，那么合法括号需要增加2，可能是这一对括号之前的基础上加，也可能这一对就是起点，因此转移公式为： $d p [i] = (i > = 2 ? d p [i - 2] : 0) + 2$
- 情况二：
如图所示，与该右括号匹配的左括号不在自己旁边，而是它前一个合法序列之前，因此通过下标减去它前一个的合法序列长度即可得到最前面匹配的左括号，因此转移公式为： $d p [i] = (i - d p [i - 1] > 1 ? d p [i - d p [i - 1] - 2] : 0) + d p [i - 1] + 2$
step 4：每次检查完维护最大值即可。

这道题与打家劫舍（一）比较类似，区别在于这道题是环形，第一家和最后一家是相邻的，既然如此，在原先的方案中第一家和最后一家不能同时取到。

step 1：使用原先的方案是：用dp[i]表示长度为i的数组，最多能偷取到多少钱，只要每次转移状态逐渐累加就可以得到整个数组能偷取的钱。
step 2：（初始状态） 如果数组长度为1，只有一家人，肯定是把这家人偷了，收益最大，因此 $d p [1] = n u m s [0]$ 。
step 3：（状态转移） 每次对于一个人家，我们选择偷他或者不偷他，如果我们选择偷那么前一家必定不能偷，因此累加的上上级的最多收益，同理如果选择不偷他，那我们最多可以累加上一级的收益。因此转移方程为 $d p [i] = m a x (d p [i - 1], n u m s [i - 1] + d p [i - 2])$ 。这里的i在dp中为数组长度，在nums中为下标。
step 4：此时第一家与最后一家不能同时取到，那么我们可以分成两种情况讨论：
- 情况1：偷第一家的钱，不偷最后一家的钱。初始状态与状态转移不变，只是遍历的时候数组最后一位不去遍历。
- 情况2：偷最后一家的请，不偷第一家的钱。初始状态就设定了 $d p [1] = 0$ ，第一家就不要了，然后遍历的时候也会遍历到数组最后一位。
step 5：最后取两种情况的较大值即可。