Luyện tập #5
Bài học 14 trên 14 trong khóa học Danh sách liên kết, loạt bài về cấu trúc dữ liệu #5 của Coddy.
Thử thách
DễCho một mảng số nguyên arr (các giá trị của danh sách liên kết) và một số nguyên dương n, hãy viết hàm nthFromEnd trả về giá trị của nút thứ n tính từ cuối danh sách (đánh số từ 1).
Nếu n nằm ngoài phạm vi (bằng không, âm hoặc lớn hơn độ dài danh sách), hãy trả về -1.
Hãy dùng danh sách liên kết để giải bài toán này! Mẹo hai con trỏ kinh điển giúp bạn không cần duyệt danh sách để đếm độ dài.
Bạn phải dùng lớp LinkedList (được cung cấp trong linkedlist.<ext> cùng với node.<ext>), không dùng các tính năng dựng sẵn của ngôn ngữ như đảo ngược mảng, cắt lát hoặc các thao tác với danh sách trong thư viện chuẩn để tính kết quả.
Tự làm thử
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char line1[8192];
char line2[64];
if (!fgets(line1, sizeof(line1), stdin)) line1[0] = '\0';
if (!fgets(line2, sizeof(line2), stdin)) line2[0] = '\0';
int arr[4096];
int len = 0;
char* tok = strtok(line1, " \t\r\n");
while (tok) { arr[len++] = atoi(tok); tok = strtok(NULL, " \t\r\n"); }
int n = atoi(line2);
int r = nthFromEnd(arr, len, n);
printf("%d\n", r);
return 0;
}
Tất cả bài học trong Danh sách liên kết, loạt bài về cấu trúc dữ liệu #5
Tự luyện tập: Trình biên dịch C online