【C++】1回の走査（シングルトラバーサル）でリンクリストの末尾から2番目のノードを取得する方法

この記事では、リンクリストの末尾から2番目の要素を1回の走査（シングルトラバーサル）で取得する方法を解説します。例えば、リストが [10, 52, 41, 32, 69, 58, 41] という要素を持っている場合、末尾から2番目の要素は 58 となります。

アルゴリズムの考え方

この問題を効率的に解くには、2つのポインタを使用します。1つは現在のノードを指すポインタ（curr）、もう1つは現在位置の直前のノードを指すポインタ（prev）です。curr の next が NULL になるまで両方のポインタを同時に進めていき、ループが終了した時点で prev が指しているノードこそが、求めていた末尾から2番目のノードになります。あとはそのノードの値を返すだけで処理は完了です。

この手法を使えば、リストを複数回走査する必要がなくなり、時間計算量 O(n)・空間計算量 O(1) で問題を解くことができます。なお、リストの要素数が2未満の場合は prev が NULL のままになるため、実用時にはそのケースへの対処も加えておくとより安全です。

サンプルコード

#include<iostream>
using namespace std;
class Node {
   public:
      int data;
      Node *next;
};
void prepend(Node** start, int new_data) {
   Node* new_node = new Node;
   new_node->data = new_data;
   new_node->next = NULL;
   if ((*start) != NULL){
      new_node->next = (*start);
      *start = new_node;
   }
   (*start) = new_node;
}
int secondLastElement(Node *start) {
   Node *curr = start, *prev = NULL;
   while(curr->next != NULL){
      prev = curr;
      curr = curr->next;
   }
   return prev->data;
}
int main() {
   Node* start = NULL;
   prepend(&start, 15);
   prepend(&start, 20);
   prepend(&start, 10);
   prepend(&start, 9);
   prepend(&start, 7);
   prepend(&start, 17);
   cout << "Second last element is: " << secondLastElement(start);
}

実行結果

Second last element is: 20