92. Reverse Linked List II

• Iteration

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right)
    {
        // 建立一個 dummy node
        // 並使用一個指標 prev 指向 dummy
        ListNode* dummy = new ListNode(-1);
        ListNode* prev = dummy;

        // dummy->next 接上 head
        dummy->next = head;

        // 移動 prev 到 left 節點的前一個節點
        for (int i = 0; i < left - 1; ++i)
        {
            prev = prev->next;
        }

        // cur 指向 left 節點
        ListNode* cur = prev->next;

        // 開始反轉 left 到 right 節點之間的鏈結
        // 以 1 -> 2 -> 3 -> 4 -> 5 為範例
        // left 為 2, right 為 4
        // 此時，prev 指標指向 1
        // cur 指標指向 2
        // node 指標指向 3

        for (int i = left; i < right; ++i)
        {
            // 取得 cur 節點的下一個節點 node
            ListNode* node = cur->next;

            // 將 cur 的 next 指向 node 的下一個節點
            // 也就是將 2 的下一個指向 4
            cur->next = node->next;

            // 將 node 插入到 prev 的後面
            // 將 3 的下一個指向 2
            node->next = prev->next;

            // 更新 prev 的 next 為 node
            // 將 1 的下一個指向 3
            // 第 1 次迴圈結束會得到 1 -> 3 -> 2 -> 4 -> 5
            // 第 2 次迴圈結束會得到 1 -> 4 -> 3 -> 2 -> 5
            prev->next = node;
        }
        // 此時的 linked list 為 dummy -> 1 -> 4 -> 3 -> 2 -> 5
        // 也就是回傳 dummy->next
        return dummy->next;
    }
};

• T: $O(N)$
• S: $O(1)$