# [LeetCode 25. Reverse Nodes in k-Group](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/610/week-3-july-15th-july-21st/3818/)
### Daily challenge Jul 18, 2021 (HARD)

>Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
>
>k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.
>
>You may not alter the values in the list's nodes, only nodes themselves may be changed.


:::info
**Example 1:**
**Input:** head = [1,2,3,4,5], k = 2
**Output:** [2,1,4,3,5]
:::

:::info
**Example 2:**
**Input:** head = [1,2,3,4,5], k = 3
**Output:** [3,2,1,4,5]
:::

:::info
**Example 3:**
**Input:** head = [1,2,3,4,5], k = 1
**Output:** [1,2,3,4,5]
:::

:::info
**Example 4:**
**Input:** head = [1], k = 1
**Output:** [1]
:::

:::warning
**Constraints:**
* The number of nodes in the list is in the range sz.
* 1 <= sz <= 5000
* 0 <= Node.val <= 1000
* 1 <= k <= sz
:::

---

### Approach 1 : :bulb:
**`12 ms ( 91.02% )`** **`O()`**

:::success
**相似題 :** 參考 [LeetCode 92. Reverse Linked List II](https://hackmd.io/SpRs-_hLSGK79Fe914TEoQ)
:::

計算 `Linked List` 有多少個 node 存入 `count`，總共進行 `count / K 組` Reverse，最後不足 `K` 的部分則保留。

如何進行 Reverse 的步驟參考 :arrow_up:**`相似題`** :arrow_up: ，當進行完`一組` reverse，將 **`p, start, end`** 移動到下一組的位置。

        p = start;
        start = p->next;
        end = (start != NULL) ? start->next : NULL;

最後回傳 **`dummy->next`**。

/**
 * 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* reverseKGroup(ListNode* head, int k) {
        if(k == 1 || head == NULL)  return head;
        
        ListNode* dummy = new ListNode(0, head);
        
        ListNode* p = dummy;
        ListNode* start = p->next;
        ListNode* end = start->next;
        
        // count number of nodes
        int count = 0;
        ListNode *it = head;
        while(it != NULL){
            count++;
            it = it->next;
        }
        
        for(int times=0; times<count/k; times++){
            // reverse
            for(int i=1; i<k; i++){                
                start->next = end->next;
                end->next = p->next;
                p->next = end;
                end = start->next;
            }

            // move to next group
            p = start;
            start = p->next;
            end = (start != NULL) ? start->next : NULL;
        }

        return dummy->next;
    }
};