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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        //使用头插法手动创建头结点
        ListNode* p,* newNode;
        newNode=new ListNode(*head);
        newNode->next=head;
        //先使p指向第m个结点的前一个结点
        p=newNode;
        int i=0;
        while(i<m-1&&p!=nullptr)
        {
            p=p->next;
            ++i;
        }
        //使用头插法
        if(p!=nullptr)
        {
            ListNode* temp1=p->next,* temp2;
            ListNode* rear;
            rear=p->next;
            temp2=temp1->next;
            p->next=nullptr;
            while(i<n&&temp2!=nullptr)
            {
                temp1->next=p->next;
                p->next=temp1;
                temp1=temp2;
                temp2=temp2->next;
                ++i;
            }
            if(i<n)
            {
                temp1->next=p->next;
                p->next=temp1;
                temp1=temp2;
            }
            rear->next=temp1;//将反转后的部分,注意反转后最后一个结点是原来反转部分第一个结点与未反转部分连接
            p=newNode->next;//工作指针回到头结点
            delete newNode;
            return p;
        }
        else
        {
            delete newNode;
            throw "error";
        }
    }
};