使用 C++ 在给定的单链表中从末尾找到第 K 个节点
链表是一种线性数据结构,具有多个相互连接的节点。每个节点由两个字段数据字段和下一个节点的地址组成。让我们假设我们已经给出了一个单向链表,任务是从给定单向链表的末尾找到第k个节点。例如,
输入-
1→2→3→4→7→8→9 K= 4
输出-
节点从 4th Position is − 4
说明-由于在给定的单向链表中,从末尾开始的“第4个”节点是“4”,因此我们将返回输出为“4”。
解决这个问题的方法
最初,我们给出了一个由节点组成的链表。每个节点都包含到下一个节点的数据和地址。因此,为了从末尾找到第k个节点,我们将使用两个最初指向链表头部的指针。
在遍历链表时,我们将移动一个指针,比如说“fast”,然后移动另一个指针,直到“fast”指针没有到达末尾。
函数kthNodefromTheEnd(node*head,intpos)将指向头节点的指针和位置作为参数,并从末尾返回节点。
让我们取两个指针'slow'和'fast',它们最初位于头部。
遍历链表并移动快速指针。
由于“fast”指针比“slow”指针提前两步,让我们移动两个指针,直到“fast”到达终点。
现在以慢速返回指向从末尾开始的第k个节点的值。
示例
#includeusing namespace std; class node{ public: int data; node*next; node(int d){ data=d; next=NULL; } }; void insertAthead(node*&head,int d){ node*n= new node(d); n->next= head; head=n; } void printList(node*head){ while(head!=NULL){ cout< data<<"-->"; head= head->next; } } void kthFromtheEnd(node*head, int k){ node*slow= head; node*fast= head; for(int i=0;i next; } while(fast!=NULL){ slow= slow->next; fast= fast->next; } cout<<"节点从 "< data< 输出结果 运行上面的代码将生成输出,
节点从 4th position is: 6说明-给定的链表是7→6→5→4→2→并且第k个值是“4”。因此,从末尾开始的第4个节点是'6',因此我们将返回'6'。