資料結構
網路
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 次檢視
廣告