C++で連結リストの末尾からn番目のノードを再帰的に求める方法

片方向連結リストと正の整数Nが入力として与えられたとき、再帰を利用してリストの末尾からN番目のノードを見つけるのが本記事の目的です。例えば、入力リストが a → b → c → d → e → f というノード列を持ち、Nが4である場合、末尾から4番目のノードは「c」となります。

基本的な考え方は、まずリストの最後のノードまで再帰的に辿り、再帰から戻る際（バックトラック時）にカウントを1ずつ増やしていくというものです。カウントがNと一致したタイミングで、その時点のノードへのポインタを結果として返します。

入出力シナリオ

入力 − リスト：1 → 5 → 7 → 12 → 2 → 96 → 33、N = 3

出力 − 末尾から3番目のノードは：2

説明 − 末尾から3番目のノードは「2」です。

入力 − リスト：12 → 53 → 8 → 19 → 20 → 96 → 33、N = 8

出力 − ノードは存在しません。

説明 − リストには7つのノードしか存在しないため、末尾から8番目のノードは取り得ません。

本プログラムで使用するアプローチ

このアプローチでは、まず再帰によってリストの末尾まで到達し、バックトラックの過程で静的なカウント変数を増やしていきます。そして、カウントが入力値Nと等しくなった瞬間に、現在のノードポインタを結果として格納します。

• int型のデータ部と次ノードを指すnextポインタを持つ構造体Nodeを定義します。
• 関数addtohead(Node** head, int data)は、先頭にノードを追加することで片方向連結リストを構築するために使用します。
• 上記の関数を使い、headを先頭ノードへのポインタとして片方向連結リストを作成します。
• 関数display(Node* head)は、headノードから順に連結リストの内容を出力するために使用します。
• Nを正の整数として受け取ります。
• 関数findNode(Node* head, int n1)は、headへのポインタとn1を受け取り、末尾からn1番目のノードが見つかった時点で結果を出力します。
• nlastを、末尾からn1番目のノードを指すポインタとして用意します。
• searchNthLast(head, n1, &nlast)を呼び出して対象ノードを探索します。
• 関数searchNthLast(Node* head, int n1, Node** nlast)は、headを先頭ノードとする連結リストにおける末尾からn1番目のノードへのポインタを返します。
• 静的なcount変数を用意します。
• headがNULLの場合は何もせずにreturnします。
• tmp = head->next として次のノードを取得します。
• searchNthLast(tmp, n1, nlast)を呼び出し、最後のノードまで再帰的に辿ります。
• 再帰から戻った後、countを1増やします。
• countがn1と等しくなったら、*nlast = head を設定します。
• 最後に、nlastが指すノードの値を結果として出力します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   Node* next;
};
void addtohead(Node** head, int data){
   Node* nodex = new Node;
   nodex->data = data;
   nodex->next = (*head);
   (*head) = nodex;
}
void searchNthLast(Node* head, int n1, Node** nlast){
   static int count=0;
   if (head==NULL){
      return;
   }
   Node* tmp=head->next;
   searchNthLast(tmp, n1, nlast);
   count = count + 1;
   if (count == n1){
      *nlast = head;
   }
}
void findNode(Node* head, int n1){
   Node* nlast = NULL;
   searchNthLast(head, n1, &nlast);
   if (nlast == NULL){
      cout << "Node does not exists";
   }
   else{
      cout << "Nth Node from the last is: "<< nlast->data;
   }
}
void display(Node* head){
   Node* curr = head;
   if (curr != NULL){
      cout<<curr->data<<" ";
      display(curr->next);
   }
}
int main(){
   Node* head = NULL;
   addtohead(&head, 20);
   addtohead(&head, 12);
   addtohead(&head, 15);
   addtohead(&head, 8);
   addtohead(&head, 10);
   addtohead(&head, 4);
   addtohead(&head, 5);
   int N = 2;
   cout<<"Linked list is :"<<endl;
   display(head);
   cout<<endl;
   findNode(head, N);
   return 0;
}

出力

上記のコードを実行すると、以下のような出力が得られます。

Linked list is :
5 4 10 8 15 12 20
Nth Node from the last is: 12

計算量と実装上の注意点

このアルゴリズムの時間計算量はO(n)です（nはリスト内のノード数）。また、再帰呼び出しの深さがリストの長さに依存するため、再帰スタック分の空間計算量もO(n)となります。

なお、count変数をstaticとして宣言しているため、同じプログラム内でsearchNthLastを複数回呼び出す場合には、呼び出し前にcountを0にリセットする処理が必要になる点に注意してください。