題目網址：https://leetcode.cn/problems/reverse-linked-list-ii/

題意：給一 single linked list 的 head 和兩整數 left 和 right, 其中 left ≤ right, 反轉位置 left 到位置 right 的 node, 並返回反轉後的 linked list。

Solution:

想法：分成三步驟

  • 將待反轉的區域反轉

  • 將 left (leftPrev->next) 的 next 指向 cur

  • 將 leftPre 的 next 指向 reverseHead

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode *dummy = new ListNode(0, head);
        ListNode *leftPrev = dummy, *cur = head;

        // loop 做完後, leftPrev 指向 left 前一個 node, cur 則指向 left
        for (int i = 0; i < left - 1; ++i) {
            leftPrev = cur;
            cur = cur->next;
        }

        // 做完 reverse 後, cur 會指向 right 後一個 node
        const auto reverseHead = reverse(cur, left, right);
        leftPrev->next->next = cur; // 將 reverse 前的 head 指向 right 後一個 node
        leftPrev->next = reverseHead;

        return dummy->next;
    }

private:
    ListNode* reverse(ListNode*& head, const int left, const int right){
        ListNode *prev = nullptr, *nxt = nullptr;

        for (int i = 0; i < right - left + 1; ++i) {
            nxt = head->next;
            head->next = prev;
            prev = head;
            head = nxt;
        }

        return prev;
    }
};
  • time：$O(n)$ ➔ 遍歷整個 linked list
  • space：$O(1)$ ➔ 只需常數空間