# 92 - Reverse Linked List II

解法一 - Iterative 解

這題的思考方法如下：

1. 首先，因為 1 $\leq$ m $\leq$ n $\leq$ length of list，head 是有可能被改動的，所以需要創造一個 dummy，讓 head 跟一般 node 一樣容易使用

2. 因為我們需要 reverse m~n 之間的 node，所以需要 prev 跟 next 來幫忙。

3. 因為 reverse 完之後，還得接出對的 list，所以需要紀錄 m 之前的 node (nodeBeforeRev) 跟 n 之後的 node (nodeAfterRev)。

img

/**
 * 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) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;

        // Go through the list, reverse the nodes between range(m,n)
        ListNode *nodeBeforeRev=dummy, *nodeAfterRev, *newFront, *newTail;
        ListNode *prev = dummy, *next; // for list reversal

        for(int i=1; i<=n; i++) {
            if(i < m) {
                nodeBeforeRev = nodeBeforeRev->next;
                prev = prev->next;
                head = head->next;
            }
            if(m == i) newTail = head;

            if(i >= m) {   
                next = head->next;
                head->next = prev;

                prev = head;
                head = next;
            }
        }
        newFront = prev;
        nodeAfterRev = head;

        // Relink the newFront and newTail
        nodeBeforeRev->next = newFront;
        newTail->next = nodeAfterRev;

        ListNode* newHead = dummy->next;
        delete dummy;
        return newHead;
    }
};

這樣解的時間效率很不錯，不過空間上就不是那麼好：

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Reverse Linked List II. Memory Usage: 8.7 MB, less than 56.45% of C++ online submissions for Reverse Linked List II.

解法二 - Recursion

reverse 類的問題常常也可以用 recursion 來解決，比如說要 reverse 一個 array，我們可以先交換頭跟尾的兩個 element，等到頭跟尾交換完，我們的子問題就變成扣掉頭跟尾兩個 element 的剩餘 array．

同理我們也可以對 linked list 中要 reverse 的部分用同樣的方式處理：

https://leetcode.com/articles/reverse-linked-list-ii/