Cách phân tách Linked List cho trước trong C++

Linked List: cấu trúc dữ liệu tuyến tính, mỗi node có khối dữ liệu và con trỏ next.

Cho Linked List, nhiệm vụ: phân tách (segregate) → tách node index lẻ và index chẵn. Index bắt đầu từ 1.

Cách tiếp cận

• 3 con trỏ: oddIndex, evenIndex, evenHead
• Duyệt list, cập nhật next pointers
• oddIndex->next = evenIndex->next
• evenIndex->next = oddIndex->next
• Cuối cùng nối oddIndex->next = evenHead

Code C++

#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) return NULL;
    node* oddIndex = head;
    node* evenIndex = head->next;
    node* evenHead = evenIndex;
    while (evenIndex && evenIndex->next) {
        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) {
        cout << head->data << "->";
        head = head->next;
    }
}

int main() {
    node* head = NULL;
    insertAtNode(head, 5);
    insertAtNode(head, 8);
    insertAtNode(head, 3);
    insertAtNode(head, 1);
    insertAtNode(head, 2);
    print(head); cout << endl;
    segregateList(head);
    print(head);
}

Kết quả

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

List gốc: 2→1→3→8→5. Sau segregate: 2→3→5→1→8 (odd indices trước, even indices sau).