C++で特定のリンクリストを分離する方法

リンクリストは線形データ構造であり、各ノードには2つのブロックがあり、一方のブロックにはノードの値またはデータが含まれ、もう一方のブロックには次のフィールドのアドレスが含まれます。

各ノードにデータと、リンクリストの次のノードを指すポインタが含まれるようなリンクリストがあると仮定します。タスクは、指定されたリンクリストを分離することです。リンクリストを分離するということは、リスト内の奇数のインデックスノードと偶数のインデックスノードを分離する必要があることを意味します。

この問題を解決するためのアプローチ

特定のリンクリストを分離するために、奇数インデックス、偶数インデックス、および偶数インデックスの値にそれぞれ3つのポインタを導入します。その後、リンクリスト全体を反復処理し、ポインタを何らかの値で初期化します。

リンクリストでは、インデックスは「1」から始まります。したがって、特定の文字列の場合、リストの最初のノードは常に奇数のインデックスノードとして扱われます。ただし、次のノードは偶数のインデックス付きノードとして扱われます。

• データと次のノードへのポインタを含むリンクリストを作成します。
• 関数segregateList（listnode * head）は、ヘッドノードへのポインターを受け取り、分離されたリンクリストを出力として返します。
• 現在リストの先頭を指している3つのポインターoddIndex、evenIndex、evenHeadを初期化します。
• リンクリスト全体を反復処理し、oddIndexの次のポインターをevenIndexの次のポインターで初期化します。
• リスト全体を繰り返し処理し、evenIndexの次のポインターをoddIndexの次のポインターで初期化します。
• ヘッドポインタを返します。

例

#include <iostream>
using namespace std;
class node {
   public:
      int data;
   node * next;
   node(int d) {
      data = d;
      next = NULL;
   }
};
node * segregateList(node * head) {
   if (head == NULL) {
      return NULL;
   }
   node * oddIndex = head;
   node * evenIndex = head -> next;
   node * evenHead = evenIndex;
   while (evenIndex != NULL and evenIndex -> next != NULL) {
      oddIndex -> next = evenIndex -> next;
      oddIndex = oddIndex -> next;
      evenIndex -> next = oddIndex -> next;
      evenIndex = evenIndex -> next;
   }
   oddIndex -> next = evenHead;
   return head;
}
void insertAtNode(node * & head, int data) {
   node * n = new node(data);
   n -> next = head;
   head = n;
}
void print(node * head) {
   while (head != NULL) {
      cout << head -> data << "->";
      head = head -> next;
   }
}
int main() {
   node * head = NULL;
   // It could be possible that the head node contains NULL Value.
   insertAtNode(head, 5);
   insertAtNode(head, 8);
   insertAtNode(head, 3);
   insertAtNode(head, 1);
   insertAtNode(head, 2);
   print(head);
   cout << endl;
   segregateList(head);
   print(head);
}

上記のコードを実行すると、次のように出力が生成されます

出力

2->3->5->1->8->

指定されたリンクリストは、2-> 1-> 3->8->5->です。リンクリストを分離すると、2-> 3-> 5->1->8->として出力が生成されます。