Trong những bài trước, khi một danh sách liên kết đơn được cài đặt mặc định cho danh sách này sẽ được duyệt từ đầu danh sách cho đến cuối danh sách liên kết đơn. Tuy nhiên trong một số trường hợp, ta cần duyệt ngược lại danh sách đó. Trong bài này, ta sẽ cùng nhau xử lý một số yêu cầu về duyệt ngược lại danh sách liên kết đơn từ cuối về đầu danh sách bằng phương pháp đảo ngược danh sách liên kết đơn.

1.Cách đảo ngược danh sách liên kết đơn

Giả sử ban đầu, danh sách liên kết đơn của tôi bao gồm các NODE (hay các phần tử) được minh họa ở hình dưới đây.

Khi thực hiện thao tác duyệt danh sách liên kết đơn trên và hiển thị ra dữ liệu có trong các NODE, kết quả nhận được sẽ có thứ tự là: A->B->C->D->NULL

Tuy nhiên, vấn đề đặt ra rằng ta cần duyện ngược lại (hay đảo ngược) danh sách liên kết đơn trên để mong muốn nhận được kết quả sẽ có thứ tự là: D->C->B->A->NULL

Để thực hiện được việc đảo ngược danh sách liên kết đơn trên ta chỉ cần hiểu đơn giản là sẽ phải thay đổi con trỏ next trong mỗi NODE bằng cách trỏ ngược lại con trỏ next để đảo ngược lại danh sách.

Nếu bạn vẫn thấy khó hiểu về việc thay đổi con trỏ trong mỗi NODE ở danh sách liên kết đơn để đảo ngược danh sách, vui lòng xem hình bên dưới:

Tóm tắt các bước đảo ngược danh sách liên kết đơn:

• Khởi tạo NODE* current chính là NODE hiện tại và gán bằng ds.pHead
• Khởi tạo NODE* prev chính là NODE trước NODE current hiện tại và gán ban đầu bằng NULL
• Khởi tạo NODE *next chính là NODE sau NODE hiện tại và gán ban đầu bằng NULL
• Duyệt toàn bộ danh sách từ đầu cho đến NULL bằng vòng lặp, sau đó trong vòng lặp thực hiện các bước sau:
  • next = current->next;
  • current->next = prev;
  • prev = current;
  • current = next;
• Bên ngoài vòng lặp gán lại phần tử đầu danh sách: ds.pHead = prev;

2.Hàm đảo ngược danh sách liên kết đơn

Để thực hiện việc xây dựng một hàm dùng cho việc đảo ngược danh sách liên kết đơn ta cần khởi tạo 3 node đó là: NODE* current = l.pHead; NODE *prev = NULL; NODE *next = NULL;

Hàm void DaoNguocDS(LIST &ds) nhận tham số đầu vào là danh sách cần đảo ngược LIST &ds và sau đó sẽ thực hiện việc khởi tạo và đảo ngược danh sách liên kết đơn.

void DaoNguocDS(LIST &ds){
    //khoi tao NODE hien tai
    NODE *current = ds.pHead;
    //khoi tao NODE truoc NODE hien tai
    NODE *prev = NULL;
    //khoi tao NODE sau NODE hien tai
    NODE *next = NULL;
    //duyet tu dau den cuoi danh sach
    while (current != NULL) {
        //gan next bang node phia sau node hien tai
        next = current->next;
        //gan con tro next cua node hien tai ve node phia sau no
        current->next = prev;
        //gan node phai sau bang node hien tai
        prev = current;
        //gan hien tai bang node phia sau
        current = next;
    }
    //gan lai node dau danh sach lien ket
    ds.pHead = prev;
}

3.Chương trình hoàn chỉnh đảo ngược danh sách liên kết đơn

Chương trình dưới đây, được kết hợp cả hai hàm đã nêu trên để thực hiện việc đảo ngược lại danh sách liên kết đơn. Chương trình ban đầu sẽ được nhập vào danh sách liên kết đơn và hiển thị ra các số theo thứ tự từ đầu đến cuối, sau khi thực hiện gọi hàm void DaoNguocDS(LIST &ds) việc hiện thị sẽ theo thứ tự từ cuối đến đầu.

#include <stdio.h>
#include <stdlib.h>
struct Node
{
    //khai bao thanh phan du lieu co kieu int
    int data;
    //khai bao con tro next co kieu Node
    Node *next;
};
typedef struct Node NODE;

struct list{
    //thanh phan dau danh sach
    NODE *pHead;
    //thanh phan cuoi danh sach
    NODE *pTail;
};
typedef struct list LIST;

void KhoiTao(LIST &ds){
    //dat dia chi dau danh sach bang NULL
    ds.pHead = NULL;
    //dat dia chi cuoi danh sach bang NULL
    ds.pTail = NULL;
}

int KiemTraRong(LIST ds){
    //neu phan tu dau danh sach NULL
    if (ds.pHead == NULL){
        //tra ve 1 la co NULL
        return 1;
    }
    //truong hop nguoc lai tra ve khong null
    return 0;
}

NODE* TaoNode(int x) {
    //tao mot node p moi
    NODE *p;
    p = new NODE;
    //neu p==NULL thi khong du bo nho
    if (p==NULL) {
        printf ("KHONG DU BO NHO");
        return NULL;
    }
    //gan thanh phan data = x
    p->data=x;
    //gan con tro next = NULL
    p->next=NULL;
    //tra ve node p da tao
    return p;
}
void ChenCuoi (LIST &ds, NODE *p){
    //neu phan tu dau rong thi danh sach rong
    if (ds.pHead==NULL) {
        //chen dau va cuoi deu bang node p
        ds.pHead=p;
        ds.pTail=p;
    }
    //nguoc lai danh sach khong rong
    else {
        //gan con tro cua phan tu cuoi trong danh sach bang node p
        ds.pTail->next=p;
        //gan pTail bang node p
        ds.pTail=p;
    }
}

void Nhap(LIST &ds, int n){
    //duyet N lan
    for(int i = 0; i < n; i++){
        //nhap du lieu la so nguyen int x
        int x;
        printf("Nhap vao so [%d]: ",i);
        scanf("%d",&x);
        //tao node p
        NODE *p = new NODE;
        //dua du lieu vua nhap vao node p
        p = TaoNode(x);
        //dua node p vao ham chen cuoi
        ChenCuoi(ds,p);
    }
}

void Xuat(LIST ds){
    //khoi tao mot node
    NODE *p = new NODE;
    //duyet tu dau danh sach den cuoi danh sach voi dieu kien p!=NULL
    for(p = ds.pHead; p!= NULL; p=p->next){
        //hien thi du lieu cua tung node
        printf("%d \t",p->data);
    }
}

void DaoNguocDS(LIST &ds){
    //khoi tao NODE hien tai
    NODE *current = ds.pHead;
    //khoi tao NODE truoc NODE hien tai
    NODE *prev = NULL;
    //khoi tao NODE sau NODE hien tai
    NODE *next = NULL;
    //duyet tu dau den cuoi danh sach
    while (current != NULL) {
        //gan next bang node phia sau node hien tai
        next = current->next;
        //gan con tro next cua node hien tai ve node phia sau no
        current->next = prev;
        //gan node phai sau bang node hien tai
        prev = current;
        //gan hien tai bang node phia sau
        current = next;
    }
    //gan lai node dau danh sach lien ket
    ds.pHead = prev;
}

int main(){
    //khai bao mot danh sach
    LIST ds;
    //nhap so luong N tu ban phim
    int n;
    printf("Nhap N: ");
    scanf("%d",&n);
    //khoi tao danh sach
    KhoiTao(ds);
    //goi ham nhap va truyen danh sach va so luong N vao
    Nhap(ds,n);
    //goi ham xuat du lieu 
    printf("DANH SACH VUA NHAP VAO LA\n");
    Xuat(ds);
    //goi ham dao nguoc danh sach va hien thi ra ket qua
    printf("\nDANH SACH DUOC DAO NGUOC LA\n");
    DaoNguocDS(ds);
    Xuat(ds);
}