LeetCode 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) {
        if(m==n) return head;                       //特殊情况
        ListNode* Vhead=new ListNode(0);            //虚拟头节点
        Vhead->next=head;
        int count=1;                                //计数
        ListNode* pre=Vhead, *now, *q;
        while(count<m){
            pre=pre->next;
            count++;
        }
        ListNode* last=pre, *nn=pre->next;                // pre -->1  记下两个边缘结点
        pre=pre->next; now=pre->next; q=now->next;              
        count++;                                          //再进一步,开始反转  
        while(count<n){
            now->next=pre;
            pre=now;
            now=q;
            q=q->next;
            count++;
        }                                                 //pre -->3 now -->4  p -->5
        now->next=pre;                                    //加上一次反转
        last->next=now;
        nn->next=q;                                       //链接边缘结点
        pre=Vhead->next;                                    
        delete Vhead;                                     //删除虚拟头节点
        return pre;
    }
};
原文地址:https://www.cnblogs.com/oneDongHua/p/14264011.html