Tìm nút thứ n từ cuối danh sách liên kết trong C

Bài toán

Cho danh sách liên kết đơn, hãy in ra nút thứ n tính từ cuối danh sách mà không thay đổi thứ tự các nút.

Ví dụ

Danh sách: 10 → 20 → 30 → 40 → 50 → 60
n = 3
Output: 40

Giải thích: Từ cuối về, nút thứ 1 là 60, thứ 2 là 50, thứ 3 là 40.

Phương pháp hiệu quả

Thay vì duyệt toàn bộ danh sách, ta dùng con trỏ tạm và bộ đếm:

• Tạo con trỏ temp trỏ đến nút đầu (head)
• Đếm tổng số nút (count)
• Di chuyển temp tới vị trí count - n
• In dữ liệu tại temp

Thuật toán

Bắt đầu
Bước 1: Định nghĩa cấu trúc node (data, next), con trỏ head, temp
Bước 2: Hàm insert(val) - chèn nút vào cuối danh sách
Bước 3: Hàm display() - hiển thị danh sách
Bước 4: Hàm last(n) - tìm nút thứ n từ cuối
    temp = head
    Với i từ 0 đến count-n-1: temp = temp->next
    In temp->data
Bước 5: main(): tạo danh sách, gọi insert, display, last(3)
Kết thúc

Mã nguồn C

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *next;
} *head, *temp;

int count = 0;

void insert(int val) {
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->data = val;
    newnode->next = NULL;
    if (head == NULL) {
        head = newnode;
        temp = head;
        count++;
    } else {
        temp->next = newnode;
        temp = temp->next;
        count++;
    }
}

void display() {
    if (head == NULL) printf("Danh sách rỗng");
    else {
        temp = head;
        while (temp != NULL) {
            printf("%d ", temp->data);
            temp = temp->next;
        }
    }
}

void last(int n) {
    int i;
    temp = head;
    for (i = 0; i < count - n; i++)
        temp = temp->next;
    printf("\nNút thứ %d từ cuối là: %d", n, temp->data);
}

int main() {
    head = NULL;
    int n = 3;
    insert(1); insert(2); insert(3);
    insert(4); insert(5); insert(6);
    printf("Danh sách: ");
    display();
    last(n);
    return 0;
}

Kết quả

Danh sách: 1 2 3 4 5 6
Nút thứ 3 từ cuối là: 4