LeetCode 92. Reverse Linked List II [Medium] [C++] 解題筆記

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

EX:

        Input: 1->2->3->4->5->NULL, m = 2, n = 4

        Output: 1->4->3->2->5->NULL

想法:

        這題基本上就是照著題意實作然後用一個 count 去紀錄現在遍歷到哪裡，這種作法會需要一堆

branch condition (if else) 判斷式，因此這題還有另一種比較炫炮的寫法可以避免 branch condition，

主要就是我們可以將迴圈拆開來，首先先遍歷到 m 的前一個位置然後紀錄下 m 的前一個位置 dummy 和 m 這個位置 tail，

因為 m 會是反轉之後的最後一個 node ，之後在遍歷 m~n 這個範圍將裡面的 node 做反轉，最後再將 tail 指向 n + 1 個 node，

dummy 指向原本的第 n 個 node(反轉後的第 m 個 node)之後就大功告成拉。

完整程式碼:

解法一:

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* cur = &dummy;
        ListNode* pre = &dummy;
        ListNode* rpre = &dummy;
        ListNode* rstart = &dummy;
        int cnt = 0;
        while (cur != nullptr) {
            auto next = cur->next;
            if (cnt == m) {
                rpre = pre;
                rstart = cur;
            }
            else if (cnt > m && cnt < n) {
                cur->next = pre;
            }
            else if (cnt == n) {
                cur->next = pre;
                rstart->next = next;
                rpre->next = cur;
            }
            pre = cur;
            cur = next;
            cnt++;
        }
        return dummy.next;
    }
};

解法二(branchless):

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *p_head = dummy;
        for (int i = 0; i < m - 1; i++) {
            dummy = dummy->next;
        }
        ListNode *pre = dummy;
        ListNode *cur = dummy->next;
        ListNode *tail = cur;
        
        for (int i = m; i <= n; i++) {
            auto next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        dummy->next = pre;
        tail->next = cur;
        
        return p_head->next;
    }
};