Với n nút, nhiệm vụ là in nút thứ n từ cuối danh sách liên kết. Chương trình không được thay đổi thứ tự của các nút trong danh sách thay vào đó nó chỉ được in nút thứ n từ nút cuối cùng của danh sách được liên kết.
Ví dụ
Input -: 10 20 30 40 50 60 N=3 Output -: 40
Trong ví dụ trên, bắt đầu từ nút đầu tiên, các nút cho đến khi đếm được n nút được duyệt qua, tức là 10,20 30,40, 50,60 và do đó nút thứ ba từ nút cuối cùng là 40.
Thay vì duyệt qua toàn bộ danh sách, bạn có thể làm theo cách tiếp cận hiệu quả này -
- Lấy một con trỏ tạm thời, giả sử, tạm thời của loại nút
- Đặt con trỏ tạm thời này thành nút đầu tiên được trỏ bởi con trỏ head
- Đặt bộ đếm số lượng nút trong danh sách
- Chuyển nhiệt độ sang tạm thời → tiếp theo cho đến đếm-n
- Hiển thị tạm thời → dữ liệu
Nếu chúng ta sử dụng cách tiếp cận này, hơn số đếm sẽ là 5 và chương trình sẽ lặp lại vòng lặp cho đến 5-3 tức là 2, vì vậy bắt đầu từ 10 vào ngày 0 vị trí hơn 20 trên 1 st vị trí và 30 vào ngày 2 nd vị trí là kết quả. Vì vậy, bằng cách tiếp cận này, không cần phải duyệt qua toàn bộ danh sách cho đến cuối sẽ tiết kiệm không gian và bộ nhớ.
Thuật toán
Start Step 1 -> create structure of a node and temp, next and head as pointer to a structure node struct node int data struct node *next, *head, *temp End Step 2 -> declare function to insert a node in a list void insert(int val) struct node* newnode = (struct node*)malloc(sizeof(struct node)) newnode->data = val IF head= NULL set head = newnode set head->next = NULL End Else Set temp=head Loop While temp->next!=NULL Set temp=temp->next End Set newnode->next=NULL Set temp->next=newnode End Step 3 -> Declare a function to display list void display() IF head=NULL Print no node End Else Set temp=head Loop While temp!=NULL Print temp->data Set temp=temp->next End End Step 4 -> declare a function to find nth node from last of a linked list void last(int n) declare int product=1, i Set temp=head Loop For i=0 and i<count-n and i++ Set temp=temp->next End Print temp->data Step 5 -> in main() Create nodes using struct node* head = NULL Declare variable n as nth to 3 Call function insert(10) to insert a node Call display() to display the list Call last(n) to find nth node from last of a list Stop
Ví dụ
#include<stdio.h>
#include<stdlib.h>
//structure of a node
struct node{
int data;
struct node *next;
}*head,*temp;
int count=0;
//function for inserting nodes into a list
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++;
}
}
//function for displaying a list
void display(){
if(head==NULL)
printf("no node ");
else {
temp=head;
while(temp!=NULL) {
printf("%d ",temp->data);
temp=temp->next;
}
}
}
//function for finding 3rd node from the last of a linked list
void last(int n){
int i;
temp=head;
for(i=0;i<count-n;i++){
temp=temp->next;
}
printf("\n%drd node from the end of linked list is : %d" ,n,temp->data);
}
int main(){
//creating list
struct node* head = NULL;
int n=3;
//inserting elements into a list
insert(1);
insert(2);
insert(3);
insert(4);
insert(5);
insert(6);
//displaying the list
printf("\nlinked list is : ");
display();
//calling function for finding nth element in a list from last
last(n);
return 0;
} Đầu ra
linked list is : 1 2 3 4 5 6 3rd node from the end of linked list is : 4