鏈錶內指定區間反轉

問題

將一個節點數為 size 鏈錶 m 比特置到 n 比特置之間的區間反轉，要求時間複雜度 O(n)，空間複雜度 O(1)。

思路

1. 采用雙指針移動到指定比特置： pre 移動到挪動區間的起始比特置的前一個比特置，cur 移動到挪動區間的起始比特置。
2. 連接 cur 與 cur 的下下個元素，斷開 cur 與 next 的連接；next 連接到 pre 後一元素之前；pre 指向 next。

代碼實現

/** * 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* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* pre = dummyHead;
        // 0 < m < size,所以本題鏈錶下標從 1 開始，pre 指向翻轉區間的起始前一個比特置
        for (int i = 1; i < m; i++)
        {
    
            pre = pre->next;
        }
        ListNode* cur = pre->next;
        
        for (int i = m; i < n; i++)
        {
    
            ListNode* next = cur->next;
            // 斷開 cur 與 next 的連接
            cur->next = next->next;
            // 將後續的 next 移動到 pre 下一個元素前
            next->next = pre->next;
            // 連接 pre 和 next
            pre->next = next;
        }
        
        return dummyHead->next;
    }
};