C++で連結リストのK個ごとのノードを交互に反転する方法

はじめに

このチュートリアルでは、長さNの連結リストAと整数Kが与えられたとき、サイズKごとのグループに分けて、交互にノードを反転する方法を解説します。なお、NはKで割り切れるものとします。関数の第1引数には連結リストAの先頭ポインタ、第2引数には整数Kが渡されます。

まず、入力と出力の例を見てみましょう。

入力例1

5 -> 6 -> 2 -> 8 -> 5 -> 2 -> 4 -> 8 -> 9 -> 6 -> null（K=2）

出力

6 -> 5 -> 2 -> 8 -> 2 -> 5 -> 4 -> 8 -> 6 -> 9 -> null

入力例2

1 -> 2 -> 5 -> 8 -> 9 -> 6 -> 4 -> 5 -> 8 -> null（K=3）

出力

5 -> 2 -> 1 -> 8 -> 9 -> 6 -> 8 -> 5 -> 4 -> null

このように、最初のK個のノードは反転され、次のK個はそのまま維持され、また次のK個が反転される——という処理がリストの終端まで繰り返されます。

解決策へのアプローチ：反復解法

• 1回のループごとに2K個のノードを走査し、joinポインタとtailポインタを使って、入力された連結リスト内の各Kノードペアの先頭と末尾を記録します。

• 次に、連結リストのK個のノードを反転し、反転後のリストの末尾ノードを、joinポインタが指す元のリストの先頭ノードと接続します。

• その後、currentポインタを次のK個のノードへ進めます。

• 通常のリストの末尾（新しいtailが指すノード）が最後のノードとして機能し、joinポインタは新しく反転されたリストの先頭を指すため、両者がマージされます。すべてのノードに対して同じ手順が完了するまで、これらのステップを繰り返します。

反復解法の実装例

#include <bits/stdc++.h>
using namespace std;
class Node {
    public:
    int data;
    Node* next;
};
Node* kAltReverse(struct Node* head, int k){
    Node* prev = NULL;
    Node* curr = head;
    Node* temp = NULL;
    Node* tail = NULL;
    Node* newHead = NULL;
    Node* join = NULL;
    int t = 0;
    while (curr) {
        t = k;
        join = curr;
        prev = NULL;
        // K個のノードを反転する
        while (curr && t--) {
            temp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = temp;
        }
        if (!newHead)
            newHead = prev;
        if (tail)
            tail->next = prev;
        tail = join;
        tail->next = curr;
        // 次のK個のノードをスキップする
        t = k;
        while (curr && t--) {
            prev = curr;
            curr = curr->next;
        }
        tail = prev;
    }
    return newHead;
}
void push(Node** head_ref, int new_data){
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
void printList(Node* node){
    int count = 0;
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
        count++;
    }
}
int main(void){
    Node* head = NULL;
    int i;
    for (i = 6; i <27; i+=3)
        push(&head, i);
    int k = 3;
    cout << "Given linked list \n";
    printList(head);
    head = kAltReverse(head, k);
    cout << "\n Modified Linked list \n";
    printList(head);
    return (0);
}

出力結果

Given linked list
24 21 18 15 12 9 6
Modified Linked list
18 21 24 15 12 9 6

再帰解法

次に、再帰を利用したアプローチを紹介します。処理の流れは以下の通りです。

• 先頭からK個のノードを走査し、temp変数にK+1番目のノードを設定します。

• 走査したK個のノードをすべて反転します。

• そのKノードグループの最後のノードのnextポインタをtempに接続します。

• スキップが必要な次のKノードグループのイテレーションを飛ばします。

• 最後のノードに到達するまで、次のK個のノードを反転するためにこれらの手順を再帰的に繰り返します。

擬似コード

reverseAltK(head, k)
    curr = head
    prev = null
    next = null
    count = 0
    WHILE count < k AND curr
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
        count = count + 1
IF head
    head.next = curr
count = 0
WHILE count < k-1 AND curr
    curr = curr.next
    count = count + 1
IF curr
    curr.next = reverseKGroupAltRecursive(curr.next, k)
return prev

再帰解法の実装例

#include <bits/stdc++.h>
using namespace std;
/* 連結リストのノード */
class node{
    public:
    int data;
    node* next;
};
/* kAltReverse() のヘルパー関数 */
node * _kAltReverse(node *node, int k, bool b);

/* 与えられた連結リストを指定されたサイズkの
   グループごとに交互に反転する */
node *kAltReverse(node *head, int k){
    return _kAltReverse(head, k, true);
}
/* kAltReverse() のヘルパー関数。
   第3引数bがtrueの場合のみリストのK個のノードを反転し、
   それ以外の場合はポインタをKノード先へ進めてから
   自身を再帰的に呼び出す */
node * _kAltReverse(node *Node, int k, bool b){
    if(Node == NULL)
        return NULL;
    int count = 1;
    node *prev = NULL;
    node *current = Node;
    node *next;
    /* このループには2つの目的がある
       1) bがtrueの場合、K個のノードを反転する
       2) bがfalseの場合、currentポインタを進めるだけ */
    while(current != NULL && count <= k){
        next = current->next;
        /* bがtrueの場合のみノードを反転する */
            if(b == true)
                current->next = prev;
        prev = current;
        current = next;
        count++;
    }
    /* 3) bがtrueの場合、NodeはK番目のノードである。
       そのため、残りのリストをNodeの後に接続する。
       4) 接続後、新しい先頭を返す */
    if(b == true){
        Node->next = _kAltReverse(current, k, !b);
        return prev;
    }
    /* bがtrueでない場合、残りのリストをprevの後に接続する */
    else{
        prev->next = _kAltReverse(current, k, !b);
        return Node;
    }
}
/* ユーティリティ関数 */
/* ノードを追加する関数 */
void push(node** head_ref, int new_data){
    /* ノードを確保する */
    node* new_node = new node();
    /* データを格納する */
    new_node->data = new_data;
    /* 古いリストを新しいノードに接続する */
    new_node->next = (*head_ref);
    /* 先頭を新しいノードに移動する */
    (*head_ref) = new_node;
}
/* 連結リストを出力する関数 */
void printList(node *node){
    int count = 0;
    while(node != NULL){
        cout << node->data << " ";
        node = node->next;
        count++;
    }
}
// ドライバーコード
int main(void){
    /* 空のリストから開始 */
    node* head = NULL;
    int i;
    // 1->2->3->4->5......->20 のリストを作成
    for(i = 20; i > 0; i--)
        push(&head, i);
    cout << "Given linked list \n";
    printList(head);
    head = kAltReverse(head, 3);
    cout << "\nModified Linked list \n";
    printList(head);
    return(0);
}

出力結果

Given linked list
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Modified Linked list
3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19

まとめ

このチュートリアルでは、単一連結リスト内の交互のKノードを反転する方法を学び、C++での擬似コードおよび実装を確認しました。このコードはJavaやPythonなど他の言語でも同様に記述できます。今回のアプローチでは、再帰を活用して交互のKノードを反転し、残りのノードをスキップする処理を実現しました。本チュートリアルが皆様のお役に立てば幸いです。