leetcode問題解:第25題Reverse Nodes in k-Group

タイトル
Reverse Nodes in k-Group
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.
Example
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
Note:

Only constant extra memory is allowed.

You may not alter the values in the list’s nodes, only nodes itself may be changed.

ぶんせき
このテーマの意味は、チェーンテーブルと正の整数kを与え、チェーンテーブルをk個毎の順序で反転させることです.すなわち、チェーンテーブルをkの長さのサブチェーンテーブルに分解し、これらのサブチェーンテーブルを反転させ、接続します.チェーンテーブルの長さがkの整数ではなく、最後の部分のサブチェーンテーブルの長さがkでない場合、この部分は反転する必要はありません.
解法
この問題について、私の考えは2つの関数を書いて問題を解決することです.

チェーンテーブルの関数を分解し、チェーンテーブルを長さkの各サブチェーンテーブル

に分解する.

は、分解後に得るサブチェーンテーブル

を反転するためにチェーンテーブルの関数を反転する.
まずチェーンテーブルを反転させる関数を実現します.この関数は比較的実現しやすく、私たちもよくこのような問題に遭遇します.実現の構想はcurrポインタでチェーンテーブルを遍歴し、preでcurrの前項を記録し、遍歴の過程でcurr->nextをpreに向け、preをcurrに割り当て、ずっと遍歴していくことで、チェーンテーブルの反転が完了し、時間複雑度がO(n)、空間複雑度がO(1)となる.
少し難しいのは、チェーンテーブルを分解する関数です.チェーンテーブルの長さが未知であるため、分解完了、反転完了後に各サブチェーンテーブルを接続する必要があります.そのため、各サブチェーンテーブルのヘッダだけでなく、各サブチェーンテーブルのテールも必要です.O(1)の空間的複雑さを満たすためには、遍歴の過程でそれぞれ2つの変数でヘッダとテールを記録するのが最も良いです.別にスペースを開くことはできません.
私の考えは:チェーンテーブルを1回遍歴して、countを通じて数えて、count ！= k時count++、遍歴を続けます;count == kになると、サブチェーンテーブルが見つかり、このサブチェーンテーブルを反転し、前に反転操作が完了したサブチェーンテーブルに接続し、countを0に設定してから、遍歴を継続する.
この中で注意すべき点はいくつかあります.

は、第1の反転後のサブチェーンテーブルのヘッダ

である最終チェーンテーブルのヘッダを記録する.

分解のたびに、サブチェーンテーブルのヘッドとテールを記録する必要がある、すなわち、curr_headとcurr_tailの

を更新する.

チェーンテーブル長がkの倍数でない場合と、kがチェーンテーブル長より大きい場合に注意する

.
これらの点が分かってからコードも実現するのは難しくないが,この解法の効率は高くないようで,チェーンテーブルを分解する効率が低いため,より良いアルゴリズムを探す必要があるはずである.
コード#コード#

class Solution {
public:
    //      
    ListNode* reverse_List(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode *curr = head, *prev = NULL;
        while (curr->next != NULL) {
            ListNode* tmp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = tmp;
        }
        curr->next = prev;
        return curr;
    }
    //          k   ，         ，      
    ListNode* reverseKGroup(ListNode* head, int k) {
        int count = 0;//           
        ListNode* tmp = head;
        ListNode* curr_head = head;//        
        ListNode* curr_tail = NULL;//             

        ListNode* result_head = NULL;

        while (tmp != NULL) {
            count++;
            if (count == k) {
                ListNode* remaining = tmp->next;
                tmp->next = NULL;
                curr_head = reverse_List(curr_head);//      
                if (result_head == NULL) result_head = curr_head;
                if (curr_tail != NULL) curr_tail->next = curr_head;
                while (curr_head->next != NULL) {
                    curr_head = curr_head->next;
                }
                curr_tail = curr_head;
                curr_head = remaining;
                tmp = remaining;
                count = 0;
            }
            else tmp = tmp->next;
        }
        //         k               
        if (count != 0 && curr_tail != NULL) curr_tail->next = curr_head;
        //   k         
        else if (count != 0 && curr_tail == NULL) return head;
        return result_head;
    }
};