【牛客题霸题解】链表内指定区间反转

做这道题目之前可以先看一下 NC78 反转链表 https://blog.nowcoder.net/n/31e6abf3dd5d4970a03f7a483ca8e0ab
先举一个例子：原链表：m = 2 ，n = 4

反转后

观察可以发现我们需要进行的步骤有以下三条：

1. 从 𝑚+1 到 𝑛 的这些节点将 𝑛𝑒𝑥𝑡 指针指向前一个节点。
2. 𝑚 节点的 𝑛𝑒𝑥𝑡 指针指向 𝑛 节点的 𝑛𝑒𝑥𝑡
3. 𝑚−1 节点的 𝑛𝑒𝑥𝑡 指针指向 𝑛 节点

然后我们来考虑两种特殊情况：
第一种：如果m和n相等，即：指定的区间只有一个节点，这个时候按这个步骤进行的话，是没有问题的
第二种：如果m=1，这时，m-1 节点是不存在的，这样就出现了问题。
为了解决这个问题，我们在链表的头节点之前再加一个空节点来指向头节点，就可以了

c++

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(m==n){return head;}
        ListNode Front(-1);
        Front.next = head;
        ListNode* MPre = &Front;
        for(int i = 0 ; i < m-1 ; i++) { MPre = MPre->next; }
        ListNode* M = MPre->next;
        ListNode* Pre = M;
        ListNode* Now = M->next;
        ListNode* Next = NULL;
        for(int i = m+1 ; i <= n ; i++){
            Next = Now->next;
            Now->next = Pre;
            if(i == n)
            {
                M->next = Next;
                MPre->next = Now;
            }
            Pre = Now;
            Now = Next;
        }
        return Front.next;
    }
};

java

import java.util.*;
public class Solution {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        if(m==n){return head;}
        ListNode Front = new ListNode(-1);
        Front.next = head;
        ListNode MPre = Front;
        for(int i = 0 ; i < m-1 ; i++) { MPre = MPre.next; }
        ListNode M = MPre.next;
        ListNode Pre = M;
        ListNode Now = M.next;
        ListNode Next = null;
        for(int i = m+1 ; i <= n ; i++){
            Next = Now.next;
            Now.next = Pre;
            if(i == n)
            {
                M.next = Next;
                MPre.next = Now;
            }
            Pre = Now;
            Now = Next;
        }
        return Front.next;
    }
}

python

class Solution:
    def reverseBetween(self , head , m , n ):
        if m==n:
            return head
        Front = ListNode(1)
        Front.next = head
        MPre = Front
        for i in range(0,m-1):
            MPre = MPre.next
        M = MPre.next
        Pre = M;
        Now = M.next
        Next = None
        for i in range(m+1,n+1):
            Next = Now.next
            Now.next = Pre
            if i == n:
                M.next = Next
                MPre.next = Now
            Pre = Now
            Now = Next
        return Front.next