如何在 C++ 中隔离给定的链表

链表是一种线性数据结构，其中每个节点有两个块，这样一个块包含节点的值或数据，另一个块包含下一个字段的地址。

让我们假设我们有一个链表，每个节点都包含数据和一个指向链表下一个节点的指针。任务是隔离给定的链表。隔离链表意味着我们必须将链表中的奇数索引节点和偶数索引节点分开。

解决这个问题的方法

为了隔离给定的链表，我们将分别为奇数索引、偶数索引和偶数索引处的值引入三个指针。之后，我们将遍历整个链表并用某个值初始化指针。

在链表中，索引从“1”开始，因此对于任何特定的字符串，列表的第一个节点将始终被视为奇数索引节点。但是，下一个节点被视为偶数索引节点。

• 取一个带有数据和指向下一个节点的指针的链表。

• 函数 segregateList(listnode *head) 获取指向头节点的指针并返回分离的链表作为输出。

• 初始化三个指针oddIndex、evenIndex 和evenHead，它们当前指向列表的头部。

• 遍历整个链表，用evenIndex的next指针初始化oddIndex的next指针。

• 现在遍历整个列表并用oddIndex 的下一个指针初始化evenIndex 的下一个指针。

• 返回头指针。

示例

#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;
   // 头节点可能包含 NULL 值。
   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->。