数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 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”。
更新于: 2021年2月5日
403 次查看
广告