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

  • Z时代
  • 2024-01-10
  • 分类：综合

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

输入-

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

输出-

节点从 4th Position is − 4

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

解决这个问题的方法

最初，我们给出了一个由节点组成的链表。每个节点都包含到下一个节点的数据和地址。因此，为了从末尾找到第 k 个节点，我们将使用两个最初指向链表头部的指针。

在遍历链表时，我们将移动一个指针，比如说“fast”，然后移动另一个指针，直到“fast”指针没有到达末尾。

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

  • 让我们取两个指针 'slow' 和 'fast'，它们最初位于头部。

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

  • 由于“fast”指针比“slow”指针提前两步，让我们移动两个指针，直到“fast”到达终点。

  • 现在以慢速返回指向从末尾开始的第 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<<"节点从 "<<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;
}
输出结果

运行上面的代码将生成输出，

节点从 4th position is: 6

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

以上是 使用 C++ 在给定的单链表中从末尾找到第 K 个节点 的全部内容， 来源链接： utcz.com/z/311471.html

回到顶部