LeetCode 25. Reverse Nodes in k-Group [Hard] [C++] 解題筆記

這題給定我們一個 linked list，與一個值 k ，要求我們以每 k 個 node 為一組 reverse 此 list。

EX:

        Given this linked list: 1->2->3->4->5

        For k = 2, you should return: 2->1->4->3->5

        For k = 3, you should return: 3->2->1->4->5

想法:

            這題基本上就是實作題，可以用 recursive 的方式遞迴計算每 k 個 node 的 reversed list。

完整程式碼:

class Solution {

public:

    ListNode* reverse(ListNode *head, ListNode *tail) {

        ListNode *pre = tail;

        while (head != tail) {

            ListNode *next = head->next;

            head->next = pre;

            pre = head;

            head = next;

        }

        return pre;

    }

    ListNode* reverseKGroup(ListNode* head, int k) {

        ListNode *cur = head;

        // after kth iterations, cur will point to k + 1th node which is the beginning of next group

        for (int i = 0; i < k; i++) {

            if (!cur) { return head;}

            cur = cur->next;

        }

        ListNode *new_head = reverse(head, cur);

        // head will become tail in this group after reverse, so it's next node is the result of next group (start from cur)

        head->next = reverseKGroup(cur, k);

        

        return new_head;

    }

};