Chương trình C đảo ngược danh sách liên kết

Trong bài toán này, chúng ta được cho một danh sách liên kết. Nhiệm vụ là viết chương trình để đảo ngược danh sách liên kết đó.

Chương trình sẽ đảo ngược danh sách liên kết đã cho và trả về danh sách liên kết đã đảo ngược.

Danh sách liên kết là một chuỗi các liên kết chứa các mục. Mỗi liên kết chứa một kết nối đến liên kết khác.

Ví dụ

9 -> 32 -> 65 -> 10 -> 85 -> NULL

Danh sách liên kết đảo ngược là danh sách liên kết được tạo thành bằng cách đảo ngược các liên kết của danh sách. Nút đầu (head) của danh sách liên kết sẽ trở thành nút cuối và nút cuối sẽ trở thành nút đầu.

Ví dụ

Danh sách liên kết đảo ngược được tạo từ danh sách liên kết trên:

85 -> 10 -> 65 -> 32 -> 9 -> NULL

Để đảo ngược danh sách liên kết đã cho, chúng ta sẽ sử dụng ba con trỏ bổ sung trong quá trình: previous (trước), after (sau), current (hiện tại).

Chúng ta khởi tạo previous và after là NULL, current là head của danh sách liên kết.

Sau đó, lặp cho đến khi đạt đến NULL của danh sách ban đầu (chưa đảo ngược) và thực hiện:

after = current -> next
current -> next = previous
previous = current
current = after

Bây giờ hãy viết chương trình đảo ngược danh sách liên kết. Có hai cách: lặp (iterative) và đệ quy (recursive).

Chương trình đảo ngược danh sách liên kết (đệ quy đuôi)

Ví dụ

#include 
struct Node {
    int data;
    struct Node* next;
};
Node* insertNode(int key) {
    Node* temp = new Node;
    temp->data = key;
    temp->next = NULL;
    return temp;
}
void tailRecRevese(Node* current, Node* previous, Node** head){
    if (!current->next) {
        *head = current;
        current->next = previous;
        return;
    }
    Node* next = current->next;
    current->next = previous;
    tailRecRevese(next, current, head);
}
void tailRecReveseLL(Node** head){
    if (!head)
        return;
    tailRecRevese(*head, NULL, head);
}
void printLinkedList(Node* head){
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}
int main(){
    Node* head1 = insertNode(9);
    head1->next = insertNode(32);
    head1->next->next = insertNode(65);
    head1->next->next->next = insertNode(10);
    head1->next->next->next->next = insertNode(85);
    printf("Linked list : \t");
    printLinkedList(head1);
    tailRecReveseLL(&head1);
    printf("Reversed linked list : \t");
    printLinkedList(head1);
    return 0;
}

Kết quả

Linked list : 9 32 65 10 85
Reversed linked list : 85 10 65 32 9

Chương trình đảo ngược danh sách liên kết (cách lặp)

Ví dụ

#include 
struct Node {
    int data;
    struct Node* next;
    Node(int data){
        this->data = data;
        next = NULL;
    }
};
struct LinkedList {
    Node* head;
    LinkedList(){
        head = NULL;
    }
    void interReverseLL(){
        Node* current = head;
        Node *prev = NULL, *after = NULL;
        while (current != NULL) {
            after = current->next;
            current->next = prev;
            prev = current;
            current = after;
        }
        head = prev;
    }
    void print() {
        struct Node* temp = head;
        while (temp != NULL) {
            printf("%d ", temp-> data);
            temp = temp->next;
        }
        printf("\n");
    }
    void push(int data){
        Node* temp = new Node(data);
        temp->next = head;
        head = temp;
    }
};
int main() {
    LinkedList linkedlist;
    linkedlist.push(85);
    linkedlist.push(10);
    linkedlist.push(65);
    linkedlist.push(32);
    linkedlist.push(9);
    printf("Linked List : \t");
    linkedlist.print();
    linkedlist.interReverseLL();
    printf("Reverse Linked List : \t");
    linkedlist.print();
    return 0;
}

Kết quả

Linked List : 9 32 65 10 85
Reverse Linked List : 85 10 65 32 9