C語言程式:查詢連結串列倒數第n個節點
給定一個包含n個節點的連結串列,任務是列印該連結串列的倒數第n個節點。程式不得改變連結串列中節點的順序,而只需要列印連結串列的倒數第n個節點。
示例
Input -: 10 20 30 40 50 60 N=3 Output -: 40
在上例中,從第一個節點開始,遍歷到count-n個節點,即10,20,30,40,50,60,所以倒數第三個節點是40。
無需遍歷整個列表,可以使用以下高效方法:
- 使用一個臨時指標,例如名為temp的節點型別指標。
- 將此temp指標設定為head指標指向的第一個節點。
- 將計數器設定為連結串列中的節點數。
- 將temp移動到temp→next,直到count-n。
- 顯示temp→data。
如果使用此方法,則count將為5,程式將迭代迴圈直到5-3,即2,所以從位置0的10開始,到位置1的20,再到位置2的30,這就是結果。因此,透過這種方法,無需遍歷整個列表到末尾,從而節省空間和記憶體。
演算法
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
示例
#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("
%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("
linked list is : "); display(); //calling function for finding nth element in a list from last last(n); return 0; }
輸出
linked list is : 1 2 3 4 5 6 3rd node from the end of linked list is : 4
廣告