# 92 - Reverse Linked List II

解法一 - In-place reversal

/**
 * 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) {
        // Corner cases, return directly
        if(head == nullptr or head->next == nullptr or m == n) {
            return head;
        }

        // Prepare dummyHead because m might be 1
        ListNode* dummyHead = new ListNode(-1);
        dummyHead->next = head;
        ListNode* prev = dummyHead;
        ListNode* cur = dummyHead->next;

        // Move to position m
        int i = 1;
        while(i < m) {
            prev = cur;
            cur = cur->next;
            ++i;
        }

        // Reverse between m to n
        ListNode* node = prev; 
        while(i <= n) {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
            ++i;
        }

        node->next->next = cur;
        node->next = prev;

        // Return the next of dummyHead;
        return dummyHead->next;
    }
};

額外補充