リンクリストペアのノードをC++でワイズスワップするプログラム

リンクリストがあるとします。隣接する2つのノード（ペア）ごとにスワップして、そのヘッドを返す必要があります。ここでの制約は、ノードの値を変更することはできず、ノード自体のみを変更できるということです。したがって、リストが[1,2,3,4]のような場合、結果のリストは[2,1,4,3]になります。

これを解決するには、次の手順に従います-

• 頭がない場合は、頭を戻します
• 最初の：=頭、2番目の：=頭の次、ダミーは値-1の1つの新しいノードです
• ダミーの次：=最初、前：=ダミー
• 2番目はnullではありません
  • temp：=次の秒
  • 次の最初：=2番目の次
  • 次の2番目：=最初
  • 次の前：=秒
  • 前：=最初
  • tempがnullでない場合は、最初の：=tempと2番目の：=tempの次、それ以外の場合は中断します
• ダミーの次を返す

理解を深めるために、次の実装を見てみましょう-

例

#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* swapPairs(ListNode* head) {
      if(!head)return head;
         ListNode* first= head;
         ListNode* second = head->next;
         ListNode* dummy = new ListNode(-1);
         dummy->next = first;
         ListNode* prev = dummy;
         while(second){
            ListNode* temp = second->next;
            first->next = second->next;
            second->next = first;
            prev->next = second;
            prev = first;
            if(temp){
               first = temp;
               second = temp ->next;
            }
            else break;
      }
      return dummy->next;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
   ListNode *head = make_list(v);
   print_list(ob.swapPairs(head));
}

入力

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

出力

[2, 1, 4, 3, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13,]