Cách tách một danh sách được liên kết nhất định trong C ++

Danh sách được liên kết là cấu trúc dữ liệu tuyến tính trong đó mỗi nút có hai khối sao cho một khối chứa giá trị hoặc dữ liệu của nút và khối còn lại chứa địa chỉ của trường tiếp theo.

Giả sử rằng chúng ta có một danh sách được liên kết sao cho mỗi nút chứa dữ liệu và một con trỏ trỏ đến nút tiếp theo của danh sách được liên kết. Nhiệm vụ là tách riêng Danh sách liên kết đã cho. Tách riêng danh sách được liên kết có nghĩa là chúng ta phải tách các nút được lập chỉ mục lẻ và các nút được lập chỉ mục chẵn trong danh sách.

Phương pháp tiếp cận để giải quyết vấn đề này

Để tách một danh sách liên kết đã cho, chúng tôi sẽ giới thiệu ba con trỏ cho chỉ mục lẻ, chỉ mục chẵn và giá trị ở chỉ mục chẵn, tương ứng. Sau đó, chúng tôi sẽ lặp lại toàn bộ danh sách được liên kết và khởi tạo con trỏ với một số giá trị.

Trong danh sách được liên kết, việc lập chỉ mục bắt đầu từ '1', do đó đối với bất kỳ chuỗi cụ thể nào, nút đầu tiên của danh sách sẽ luôn được coi là một nút được lập chỉ mục lẻ. Tuy nhiên, nút tiếp theo được coi là một nút được lập chỉ mục chẵn.

• Lấy một danh sách được liên kết với dữ liệu và con trỏ đến nút tiếp theo.
• Một function segregateList (listnode * head) đưa con trỏ đến nút head và trả về danh sách liên kết được tách biệt làm đầu ra.
• Khởi tạo ba con trỏ retailIndex, EvenIndex và EvenHead hiện đang trỏ đến đầu danh sách.
• Lặp lại trên toàn bộ danh sách được liên kết và khởi tạo con trỏ tiếp theo của retailIndex bằng con trỏ tiếp theo của EvenIndex.
• Bây giờ, hãy lặp lại toàn bộ danh sách và khởi tạo con trỏ tiếp theo của EvenIndex bằng con trỏ tiếp theo của retailIndex.
• Trả lại con trỏ đầu.

Ví dụ

#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);
}

Chạy đoạn mã trên sẽ tạo ra kết quả là,

Đầu ra

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

Danh sách liên kết đã cho là, 2-> 1-> 3-> 8-> 5->. Sau khi tách riêng danh sách được liên kết, nó sẽ tạo ra kết quả là, 2-> 3-> 5-> 1-> 8->.