25 - Reverse Nodes in k-Group

解法一 - In-place reversal

主要 reverse 的地方寫法跟前兩題一樣,要額外注意的就是如何控制一次只 reverse k 個 node。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // Count the total number of list
        int n = 0;
        for(ListNode* ptr = head; ptr != nullptr; ++n) {
            ptr = ptr->next;
        }

        // reverse group of k one at a time
        ListNode* dummyHead = new ListNode(-1);
        dummyHead->next = head;
        ListNode* prev = dummyHead;
        ListNode* cur = dummyHead->next;

        for(int i = 0; i + k <= n; i += k) {
            ListNode* node = prev;
            for(int j = 0; j < k; ++j) {
                ListNode* next = cur->next;
                cur->next = prev;
                prev = cur;
                cur = next;
            }
            node->next->next = cur;
            ListNode* tmp = prev;
            prev = node->next;
            node->next = tmp;
        }

        return dummyHead->next;
    }
};

results matching ""

    No results matching ""