C++で連結リストの位置mからnまでを1パスで反転する方法

問題概要

連結リスト（リンクリスト）が与えられたとき、位置 m から n までのノードを反転させることを考えます。ただし、この操作は1回の走査（ワンパス）で完了させる必要があります。

例えば、リストが [1,2,3,4,5] で m = 2、n = 4 の場合、結果は [1,4,3,2,5] となります。

アルゴリズムの考え方

この問題は、次の2つのメソッドを組み合わせて解きます。reverseBetween() がメインのエントリポイントとなり、内部で補助メソッド reverseN() を利用します。

• reverseN()： 先頭から数えて n 個のノードを再帰的に反転するメソッド
• reverseBetween()： 位置 m から n までの範囲の反転を担当するメインメソッド

reverseN() の処理手順

1. 後続ノードを記録するためのポインタ successor を NULL として定義します。
2. n == 1 の場合（再帰の終了条件）、successor に head の次のノードを代入し、head を返します。
3. last = reverseN(head->next, n - 1) として再帰呼び出しを行い、反転後の新しい先頭を取得します。
4. head->next->next = head でポインタをつなぎ替え、head->next = successor で反転した部分と残りのリストを接続して last を返します。

reverseBetween() の処理手順

1. m == 1 の場合、そのまま reverseN(head, n) を返します。
2. それ以外の場合、head->next = reverseBetween(head->next, m - 1, n - 1) として再帰的に処理を進め、開始位置 m に到達するまでリストを辿ります。

この再帰的なアプローチにより、リスト全体を事前に走査することなく、目的の区間だけを効率的に反転できます。時間計算量は O(n)、再帰によるスタック使用を除けば追加の空間計算量は O(1) です。

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){
           cout << ptr->val << ", ";
           ptr = ptr->next;
       }
       cout << "]" << endl;
 }
 class Solution {
    public:
        ListNode* successor = NULL;
        ListNode* reverseN(ListNode* head, int n ){
           if(n == 1){
              successor = head->next;
              return head;
           }
           ListNode* last = reverseN(head->next, n - 1);
           head->next->next = head;
           head->next = successor;
           return last;
        }
        ListNode* reverseBetween(ListNode* head, int m, int n) {
    if(m == 1){
           return reverseN(head, n);
    }
    head->next = reverseBetween(head->next, m - 1, n - 1);
            return head;
  }
};
main(){
    Solution ob;
    vector<int> v = {1,2,3,4,5,6,7,8};
    ListNode *head = make_list(v);
    print_list(ob.reverseBetween(head, 2, 6));
}

入力

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

出力

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

まとめ

この実装では、再帰を活用することで位置 m から n までのノードを1回の走査で反転できました。successor ポインタによって反転区間の末尾と残りのリストを正しく接続している点がポイントです。リンクリストの部分反転は技術面接でも頻出のテーマなので、再帰の流れをしっかり理解しておくと役立ちます。