Leetcode — 25. Reverse Nodes in k-Group (Chinese Version)

問題連結在此: https://leetcode.com/problems/reverse-nodes-in-k-group/

題目會給予一個Linked List, 以及一個整數k 要求我們每遇到k個node, 就把他們顛倒 (若總共沒有k個nodes, 則就不需要顛倒)

For example, 1->2->3->4->5 跟 k=2 
應output: 2->1->4->3->5

這題的難度是Hard
所以其實蠻建議 在解這題前
先解決的了難度中等的92. Reverse Linked List II 或讀過我的前一篇 Leetcode — 92. Reverse Linked List II (Chinese version)
再來挑戰
* 以下的solution 將會用了在上述story中提到的方法的延伸版

我覺得解這種題型, 對我來說 最挑戰的是你要怎麼一直準確地抓著你要的node 又能正確的把其他node連在一起

我的程式邏輯:

第一個想法是這題真的有點像上述的leetcode第92題, 只需要reverse一部分, 如果總長度是7, k是3的話, 那總共要reverse 2次, 分別為m=1, n=3 跟 m=4, n=6.

因為這是一個Singly Linked List, 除非我們traverse過整個list, 不然我們不會知道我們何時開始要進行reverse

但我們至少可以知道的是 "開始reverse的起點" (命名為revHead)

而決定我們何時下手開始reverse 則是用count來幫我們數目前有幾個node了 如果count = k時, 代表現在就要 reverse 從 revHead到目前所在node 的部分

* 我這次的code 奇怪的變數比較多 所以我想先解釋一下各變數名稱意義 —

* dummy - 就是一個dummy node, 預設是指向head, 會讓他指向最後結果的頭, 因此最後就是return dummy.next
* node - 我們traverse整個linked list的一個node 如果node=null就結束迴圈 
* revHead - "這次"reverse時的起點 
* preRevHead - 要reverse的部分的前一個node (不包含在這次reverse)
* Xnode - "這次"reverse時的終點 
* Ynode - reverse的後一個node (不包含在這次reverse)
所以在reverse 前,長這樣:
... -> preRevHead -> revHead -> ... ->Xnode -> Ynode -> ...
reverse後 我們希望可以變成這樣: 
... -> preRevHead -> Xnode -> ... -> revHead -> Ynode -> ...

以下是我的0ms 的code, 贏過100%的程式碼:

public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null || head.next==null || k==1 )
            return head;
        ListNode dummy = new ListNode(0,head);
        int count = 1;
        ListNode node = head;
        
        ListNode preRevHead = dummy;
        ListNode revHead = node; 
        while(node!=null)
        {
            if(count<k) 
            {
                count++;
                node = node.next;
                continue;
            }
            //when count ==k, we start to reverse! 
            ListNode xNode = node;
            ListNode yNode = node.next;
            //start to do reverse from revHead to xNode
            ListNode pre = null;
            ListNode cur = revHead;
            for(int i=0;i<k;i++)
            {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            //now pre is the new head of reversed list
            preRevHead.next = pre;
            revHead.next = yNode;
            //update preRevHead and revHead
            preRevHead = revHead;
            revHead = yNode;
            
            //node be the next node and continue traversing the list
            node = yNode;
            count = 1;
        }
        
        
        return dummy.next;
    }

時間複雜度是O(n)
空間複雜度是O(1) ✌️