题解 | #链表内指定区间反转#

题目描述
将一个链表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≤链表长度

（参考杭电 De梦的题解）

方法一：直接暴力求解

求解思路
对于反转链表，我们在求解的时候，可以引入一个next节点，然后对链表的局部进行反转。这样暴力求解，即可求出答案。

解题代码

import java.util.*;
public class Solution {
       // 参考De梦代码
    public ListNode reverseBetween (ListNode head, int m, int n) {

        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode pre = dummyNode;
        //pre结点走到m的前一个结点
        for(int i=0;i<m-1;i++){
            pre = pre.next;
        }

        //rightnode走到n的结点
        ListNode rigthNode = pre;
        for(int i=0;i<n-m+1;i++){
            rigthNode = rigthNode.next;
        }

        //取子链表
        ListNode leftNode = pre.next;
        ListNode cur = rigthNode.next;

        //分离子链表
        pre.next=null;
        rigthNode.next=null;

        //反转局部链表，参考De梦的code
        reverseLinkedList(leftNode);

        //拼接链表
        pre.next = rigthNode;
        leftNode.next = cur;
        return dummyNode.next;
    }
    //反转局部链表
    private void reverseLinkedList(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }
}

复杂度分析
时间复杂度：O(N),N为节点的个数
空间复杂度：O(1)，没有使用额外的内存空间

方法二：递归的思想求解

求解思路
对于反转链表，我们使用递归的思想，将大问题转换为小问题，然后进行相应的求解即可。对于递归过程，判断n的数值，当n为1时返回head指针，否则进行递归，并且反转链表，最后进行拼接，返回拼接之后的链表。

解题代码

class Solution {
public:
    ListNode* tmp = NULL;
    ListNode* reverseBetween(ListNode* head, int m,int n){
        if( m == 1) return reverse(head, n);
        ListNode* p = reverseBetween(head->next, m-1,n-1); // m,n在子问题中要减1
        head->next = p; //拼接反转之后的部分
        return head;
    }
    ListNode* reverse(ListNode* head,int n)
    {//反转链表，递归的思想，参考贵州大学的漫漫云天自翱翔的思路
        if(n == 1)
        {
            tmp = head->next;
            return head;
        }
        ListNode* new_head = reverse(head->next,n-1);  //子问题，位置要减1
        head->next->next = head; //反转 
        head->next = tmp;  //拼接尾部
        return new_head;
    }
};

复杂度分析
时间复杂度：一层循环，时间复杂度为O(N)
空间复杂度：其最坏递归空间复杂度为O(N).