Chuyển đổi danh sách liên kết đơn thành danh sách liên kết vòng trong C++

Trong hướng dẫn này, chúng ta sẽ thảo luận về chương trình chuyển đổi danh sách liên kết đơn (singly linked list) thành danh sách liên kết vòng (circular linked list).

Ý tưởng chính

Chúng ta được cung cấp một danh sách liên kết đơn. Nhiệm vụ là lấy các phần tử của danh sách đó và chuyển đổi nó thành danh sách liên kết vòng, nơi nút cuối cùng trỏ lại nút đầu tiên thay vì NULL.

Ví dụ minh họa

#include <bits/stdc++.h>
// Cấu trúc nút của danh sách liên kết
struct Node {
    int data;
    struct Node* next;
};

// Chuyển đổi danh sách liên kết đơn sang vòng
struct Node* circular(struct Node* head) {
    struct Node* start = head;
    // Duyệt đến nút cuối cùng
    while (head->next != NULL)
        head = head->next;
    // Gán nút cuối trỏ về nút đầu
    head->next = start;
    return start;
}

void push(struct Node** head, int data) {
    // Tạo nút mới
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = (*head);
    (*head) = newNode;
}

// Hiển thị các phần tử của danh sách liên kết vòng
void print_list(struct Node* node) {
    struct Node* start = node;
    while (node->next != start) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("%d ", node->data);
}

int main() {
    struct Node* head = NULL;
    push(&head, 15);
    push(&head, 14);
    push(&head, 13);
    push(&head, 22);
    push(&head, 17);
    circular(head);
    printf("Display list: \n");
    print_list(head);
    return 0;
}

Kết quả

Display list: 17 22 13 14 15

Giải thích: Danh sách ban đầu được xây dựng bằng cách chèn vào đầu (push), nên thứ tự là 17, 22, 13, 14, 15. Sau khi gọi circular(), nút cuối (15) trỏ về nút đầu (17), tạo thành danh sách vòng.