92反转链表

92. 反转链表 II

下面是题目

下面是题目给出的代码模板

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        
    }
};

我的解法，和重排列表有相似之处， 1切断，2反转，3合并

 //拿 1 2 3 4 5 6 ； m = 2 ，n = 5来讲解
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //递归，首先要给出返回条件
        if (head == NULL || head->next == NULL) {
            return head;
        }
        //先建立ret节点 ，实现从第二个结点开始的 递归操作
        ListNode* ret = reverseList(head->next);
        //进行反转操作，用head的next指向head本身，实现闭环
        head->next->next = head;
        // 最后
        head->next = NULL;
        return ret;
    }
   	
    ListNode* reverseBetween(ListNode* head, int m, int n) {
       //首先，把干扰全部去除，特殊条件有不少，当m==n说明不用反转
        //当只有一个节点，说明不用反转
        //当head为空，返回空
        if(m==n||!head->next)return head;
        if(!head ) return NULL;
        
        //然后利用双指针，精确的截取需要反转的链表，然后实现主、子脱钩
        //在脱钩之前，再用两个temp指针，分别指向快慢指针的下一个指针，这样让后续的再合并提供方便！
        //这里有个小细节，我先让快指针走，走n格，然后fast->next = NULL
        //然后让慢指针走，否则，一旦slow->next = NULL,快指针就不知道跑到那里去了
        int i = 0,j = 0;
        ListNode *dummy = new ListNode(0);
        dummy->next =head;
        ListNode *slow = dummy,*fast = dummy;
        while( j<n )
        {
            fast= fast->next;
            j++;
        }
        //现在fast移动到了5处
        ListNode *temp2= fast->next;//temp2 为6节点
        //实现快节点脱钩，现在，temp2和它之后的链表成为了一个新链表
        fast->next = NULL;
        /------------------------------------------------/
        while(i <m-1)
        {
            i++;
            slow = slow->next;
        }
        //现在slow指向2的前面一个节点，也就是1节点
        ListNode *temp1 = slow->next;//temp1 为2
        slow->next = NULL;
        //实现慢节点脱钩，现在，2-3-4-5 是一个新的链表了，我们现在就是要把三个再组合
        //先让fast == temp1 也是为了方便，因为反转链表之后，temp1的位置就是原来fast的位置，也就是5，所以等于是交换fast和temp1的值
        fast = temp1;//现在fast 和 temp 都为2
        temp1 = reverseList(temp1);//反转链表之后，temp1 变成了5
        //现在只要做简单的拼接就可以了
		//slow(1)指向temp1（5）
        slow->next = temp1;
        //fast(2)指向temp（2）
        fast->next =temp2;
        return dummy->next;
    }
};