LeetCode 25, 206 翻轉鏈表！

最近在衝刺Hard題，看到蠻有趣的題目就來分享一下。其實25就是206的延伸版，然後翻來翻去蠻好玩的，但如果想像力有點吃緊可以考慮玩這個網站，也許可以幫你分擔一點壓力。

我原本要用這個當示範，但一方面他不能直接嵌入，一方面你們閱讀上流量會爆炸，所以就算了XD

先來解決簡單的

206. Reverse Linked List

題目描述

給一個單向鏈表，將其反轉並返回反轉後的鏈表頭節點。

思路

我會將過程分解成以下過程（以範例1-2-3-4-5為例）：

1. 初始化：將next拆出來，把head後面清掉

   head: 1
   next: 2-3-4-5
   

2. 開始反轉：先把next的next留下

   head: 1
   next: 2
   temp: 3-4-5
   

3. 接著需要把頭接到孤零零的next上

   head: 1
   next: 2-1
   temp: 3-4-5
   

4. 然後就會發現next變成新的頭，而temp是下一個要處理的節點，所以可以直接塞回指標裡面

   head: 2-1
   next: 3-4-5
   

5. 重複上述步驟(2~4)直到next為空就會變成解答！

完整程式

Accepted
Runtime: 0ms (Beats 100.00%)
Memory: 13.38MB (Beats 68.93%)

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr){
            return nullptr;
        }
        ListNode* next = head->next;
        head->next = nullptr;
        while(next != nullptr){
            ListNode* temp = next->next;
            next->next = head;
            head = next;
            next = temp;
        }
        return head;
    }
};

25. Reverse Nodes in k-Group

題目描述

給一個單向鏈表和一個整數k，將鏈表中的節點每k個一組進行反轉，並返回反轉後的鏈表頭節點。如果剩餘節點數量不足k個，則保持原樣。

思路

這題其實用206的方式k個k個翻就翻成了，但有個小技巧：在做初始化的時候

1. 要先檢查長度（這交給你展現了），長度不夠的話要原樣丟回去（找到不會更新到head的方式）。
2. 用206的方式初始化，但是不用把head清掉，要把第k個(從0開始算)開始的反轉接在head後面，他就會被很合理的接上去了（遞迴…

這題實作其實並不複雜，只是要想出個合理的做法而已！快去試試看吧！

完整程式

Accepted
Runtime: 0ms (Beats 100.00%)
Memory: 16.41MB (Beats 69.74%)

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* tail = head;
        for(int i = 0; i < k; i++){
            if(tail == nullptr) return head;
            tail = tail->next;
        }
        ListNode* next = head->next;
        head->next = reverseKGroup(tail, k);
        for(int i = 1; i < k; i++){
            ListNode* temp = next->next;
            next->next = head;
            head = next;
            next = temp;
        }
        return head;
    }
};