使用 C++ 查找给定单链表中从末尾开始的第 K 个节点

链表是一种线性数据结构，包含多个相互连接的节点。每个节点包含两个字段：数据字段和下一个节点的地址。假设我们给定一个单链表，任务是找到给定单链表中从末尾开始的第 k 个节点。例如：

输入 -

1→2→3→4→7→8→9
K= 4

输出 -

Node from the 4th Position is − 4

解释 - 由于在给定的单链表中，从末尾开始的第“4”个节点是“4”，因此我们将输出“4”。

解决此问题的方法

最初，我们给定一个包含节点的链表。每个节点包含数据和指向下一个节点的地址。因此，要查找从末尾开始的第 k 个节点，我们将使用两个指针，它们最初都指向链表的头部。

在遍历链表时，我们将移动其中一个指针，例如“快指针”，然后移动另一个指针，直到“快指针”到达末尾。

• 函数 kthNodefromTheEnd(node*head, int pos) 以指向头节点的指针和位置作为参数，并返回从末尾开始的节点。

• 让我们使用两个指针“慢指针”和“快指针”，它们最初都在头部。

• 遍历链表并移动快指针。

• 由于“快指针”比“慢指针”领先两步，因此让我们移动这两个指针，直到“快指针”到达末尾。

• 现在返回慢指针处的值，该指针指向从末尾开始的第 k 个节点。

示例

 实时演示

#include<iostream>
using 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<<head->data<<"-->";
      head= head->next;
   }
}
void kthFromtheEnd(node*head, int k){
   node*slow= head;
   node*fast= head;
   for(int i=0;i<k;i++){
      fast= fast->next;
   }
   while(fast!=NULL){
      slow= slow->next;
      fast= fast->next;
   }
   cout<<"Node from the "<<k<<"th position is"<<slow->data<<endl;
}
int main(){
   node*head= NULL;
   insertAthead(head,2);
   insertAthead(head,4);
   insertAthead(head,5);
   insertAthead(head,6);
   insertAthead(head,7);
   printList(head);
   cout<<endl;
   kthFromtheEnd(head,4);
   return 0;
}

输出

运行以上代码将生成以下输出：

Node from the 4th position is: 6

解释 - 给定的链表是 7→ 6→ 5→ 4→ 2→，第 k 个值为“4”。因此，从末尾开始的第 4 个节点是“6”，因此我们将返回“6”。

Dev Prakash Sharma

更新于: 2021年2月5日

403 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习