好资源导航 » 文章资讯 » 使用 C++ 在给定的单链表中从末尾找到第 K 个节点

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

2023-06-21 10:18:03 86

链表是一种线性数据结构，具有多个相互连接的节点。每个节点由两个字段数据字段和下一个节点的地址组成。让我们假设我们已经给出了一个单向链表，任务是从给定单向链表的末尾找到第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个节点的值。

示例

#include
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<data<<"-->";
      head= head->next;
   }
}
void kthFromtheEnd(node*head, int k){
   node*slow= head;
   node*fast= head;
   for(int i=0;inext;
   }
   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'。

返回顶部
514930285
czq8825@qq.com

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

解决这个问题的方法

示例

热门推荐

随机推荐