[LeetCode]92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

思路:

这是一道中等难度的题目。首先我们需要往前扫描找到翻转开始节点的父节点，翻转时的节点都会插入这里，所以应保存其位置到reverseInsertPos。然后，用整数NodeCounter来标定现在游标reverseCursor走到了哪个节点，当超过n时停止循环，因此这道题用一个循环是可以轻易完成的。

AC代码:

/**
 * 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(head == nullptr)
            return nullptr;
        
        ListNode dummyHeadNode(-1);
        dummyHeadNode.next = head;
        
        ListNode* reverseInsertPos= nullptr,* reverseCursor = &dummyHeadNode;
        
        int NodeCounter = 1;
        while(reverseCursor != nullptr && NodeCounter < m)
        {
            reverseCursor = reverseCursor->next;
            NodeCounter++;
        }
        reverseInsertPos = reverseCursor;
        reverseCursor = reverseCursor->next;
        NodeCounter++;
        while(reverseCursor != nullptr && reverseCursor->next != nullptr && NodeCounter <= n)
        {
            ListNode* temp = reverseCursor->next;
            reverseCursor->next = reverseCursor->next->next;
            temp->next = reverseInsertPos->next;
            reverseInsertPos->next = temp;
            NodeCounter++;
        }
        return dummyHeadNode.next;
    }
};