C ++を使用して、特定の単一リンクリストの最後からK番目のノードを検索します

リンクリストは、相互に接続された複数のノードを持つ線形データ構造です。各ノードは、データフィールドと次のノードのアドレスの2つのフィールドで構成されます。単一リンクリストを指定したと仮定します。タスクは、指定された単一リンクリストの最後からk番目のノードを見つけることです。たとえば、

入力 −

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

出力 −

Node from the 4th Position is − 4

説明 −指定された単一リンクリストでは、最後から「4番目」のノードが「4」であるため、出力を「4」として返します。

この問題を解決するためのアプローチ

最初に、ノードで構成されるリンクリストを提供しました。各ノードには、次のノードへのデータとアドレスが含まれています。したがって、最後からk番目のノードを見つけるために、最初にリンクリストの先頭を指す2つのポインターを取得します。

リンクリストを繰り返しながら、一方のポインタを「高速」と言って移動し、もう一方のポインタを「高速」ポインタが最後に到達しなくなるまで移動します。

• 関数kthNodefromTheEnd（node * head、int pos）は、ヘッドノードへのポインターと位置をパラメーターとして受け取り、ノードを最後から返します。

• 最初は先頭にある「遅い」と「速い」の2つのポインタを見てみましょう。

• リンクリストを繰り返し処理し、高速ポインタを移動します。

• 「速い」ポインタは「遅い」より2ステップ進んでいるので、「速い」が最後に達するまで両方のポインタを動かしてみましょう。

• ここで、最後からk番目のノードを指すslowの値を返します。

例

#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」を返します。