C++で連結リストを右にk回転させるプログラムの実装方法

連結リスト（Linked List）が与えられたとき、そのリストを右方向にk回転させることを考えます。ここでkは正の整数とします。

たとえば、リストが [1 → 2 → 3 → 4 → 5 → NULL] で k = 2 の場合、出力は [4 → 5 → 1 → 2 → 3 → NULL] となります。これは末尾の2要素が先頭へ移動した状態を表しています。

アルゴリズムの手順

最も効率的なアプローチは、まずリスト全体を環状（循環リスト）につなぎ変えてから、適切な位置で切断する方法です。手順は以下の通りです。

• リストが空の場合は、nullを返す

• len := 1 と初期化する

• tail というノードを作成し、head を代入する

• tail の next が null でない限り、以下を繰り返す

  • len を 1 増やす

  • tail := tail の next

• tail の next に head を代入し、リストを環状にする

• k := k mod len（kがリスト長より大きい場合に対応）

• newHead := null と初期化する

• i が 0 から len − k まで、tail := tail の next を繰り返す

• newHead := tail の next

• tail の next := null として環状を切断する

• newHead を返す

C++での実装例

以下のコードで実際の動作を確認できます。

#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->next){
      cout << ptr->val << ", ";
      ptr = ptr->next;
   }
   cout << "]" << endl;
}
class Solution {
   public:
   ListNode* rotateRight(ListNode* head, int k) {
      if(!head) return head;
      int len = 1;
      ListNode* tail = head;
      while(tail->next){
         len++;
         tail = tail->next;
      }
      tail->next = head;
      k %= len;
      ListNode* newHead = NULL;
      for(int i = 0; i < len - k; i++){
         tail = tail->next;
      }
      newHead = tail->next;
      tail->next = NULL;
      return newHead;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,4,5,6,7,8,9};
   ListNode *head = make_list(v);
   print_list(ob.rotateRight(head, 4));
}

入力

[1,2,3,4,5,6,7,8,9], 4

出力

[6, 7, 8, 9, 1, 2, 3, 4]

処理のポイント

このアルゴリズムの計算量は O(n) です。リストを一度走査して長さを求めた後、(len − k) 回だけポインタを進めて切断位置を見つけるため、非常に効率的です。

また、k %= len を行うことで、kがリスト長よりも大きい場合でも正しく回転できる点も重要です。たとえば長さ5のリストに対して k = 7 が指定された場合、実質的には k = 2 の回転と同じ結果になります。

なお、上記の出力では末尾の「5」が表示されていません。これは補助関数 print_list が while(ptr->next) でループしているため、最後のノードを表示しない実装になっているからです。実際の回転後の完全なリストは [6, 7, 8, 9, 1, 2, 3, 4, 5] となります。