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

/**
 * 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 *ans = new ListNode(-1);
        ans->next = head;
        ListNode *leftNode = ans;
        // 定位到第m-1位;
        for(int i=0;i<m-1;++i)
        {
            leftNode = leftNode->next;
        }

        ListNode *rightNode = leftNode;
        // 定位到n+1,
        for(int i=m;i<n+1;++i)
        {
            rightNode = rightNode->next;
        }

        // 截取出一个子链表
        ListNode *temp = leftNode->next;
        ListNode *rightNode_next = rightNode->next;

        // 切断链接
        leftNode->next = NULL;
        rightNode->next = NULL;

        // 反转局部链表
        ListNode *temp_pre = NULL;
        ListNode *temp_cur = temp;
        while(temp_cur)
        {
            ListNode *temp_cur_next = temp_cur->next;
            temp_cur->next = temp_pre;
            temp_pre = temp_cur;
            temp_cur = temp_cur_next;
        }

        // 接回原来的链表
        leftNode->next = rightNode;
        temp->next = rightNode_next;

        return ans->next;
    }
};