C++で解くリンクリストのジャンプ問題：各ノードをval個先へつなぎ変える方法

問題の概要

正の整数を格納した片方向リンクリストが与えられます。このリストを処理し、各ノードの next ポインタが「そのノードの値（val）の数だけ前方にあるノード」を指すように変更します。ジャンプ先となるノードが存在しない場合は、next を NULL に設定します。

たとえば、入力が {2, 2, 3, 5, 9, 15, 3, 4} の場合、出力は [2, 3, 15] になります。これは、先頭ノード（値 2）から 2 つ先のノード（値 3）へ、さらに 3 つ先のノード（値 15）へと順番にジャンプしていき、次のジャンプでリストの範囲外に出るためそこで終了するからです。

解決のためのアプローチ

この問題は、以下の手順で解くことができます。

• 連結リストの値をすべて配列 v に格納する

• node が NULL でない間、以下を繰り返す

  • node の値を v に追加する

  • node を次のノードへ進める

• 値 0 を持つダミーノード ret を作成する

• 作業用ポインタ temp を ret に設定する

• インデックス i を 0 で初期化する

• i が配列 v のサイズ未満である間、以下を繰り返す

  • temp の next として、値 v[i] を持つ新しいノードを作成して連結する

  • temp を次のノードへ進める

  • i に v[i] を加算し、ジャンプ先のインデックスへ移動する

• 最後に ret->next を返す（ダミーノードを除いた結果のリスト）

まずリストを一度走査して配列化しておけば、あとはインデックスを飛び飛びに更新しながら新しいリストを構築するだけで済みます。時間計算量は O(n)、空間計算量も O(n) であり、シンプルで効率的な手法です。

実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class ListNode {
   public:
   int val;
   ListNode *next;
   ListNode(int data) {
      val = data;
      next = NULL;
   }
};
ListNode *make_list(vector<int> v) {
   ListNode *head = new ListNode(v[0]);
   for (int i = 1; i < v.size(); i++) {
      ListNode *ptr = head;
      while (ptr->next != NULL) {
         ptr = ptr->next;
      }
      ptr->next = new ListNode(v[i]);
   }
   return head;
}
void print_list(ListNode *head) {
   ListNode *ptr = head;
   cout << "[";
   while (ptr) {
      cout << ptr->val << ", ";
      ptr = ptr->next;
   }
   cout << "]" << endl;
}
class Solution {
   public:
   ListNode* solve(ListNode* node) {
      vector <int> v;
      while(node){
         v.push_back(node->val);
         node = node->next;
      }
      ListNode* ret = new ListNode(0);
      ListNode* temp = ret;
      int i = 0;
      while(i < v.size()){
         temp->next = new ListNode(v[i]);
         temp = temp->next;
         i += v[i];
      }
      return ret->next;
   }
};
main(){
   Solution ob;
   vector<int> v = {2,2,3,5,9,15,3,4};
   ListNode *head = make_list(v);
   print_list(ob.solve(head));
}

入力

{2,2,3,5,9,15,3,4}

出力

[2, 3, 15]