リンクリストの最後のkノードを逆の順序でC言語の再帰的アプローチで印刷します

タスクは、再帰的アプローチを使用して、リンクリストの最後からk個のノードを印刷することです。

再帰的アプローチとは、関数が呼び出しが行われるまで何度も何度も呼び出して、結果を保存するアプローチです。

たとえば、リストにノード29、34、43、56、88が含まれていて、kの値が2である場合、出力は56や88などの最後のkノードになります。

例

Linked List: 29->34->43->56->88
Input: 2
Output: 88 56

指定されているように、リストをトラバースする回数を追跡しながらリストを最後からトラバースする再帰的アプローチを使用する必要があります。再帰関数は、ポインター変数によってk番目の値まで呼び出されます。

以下のコードは、与えられたアルゴリズムのc実装を示しています。

アルゴリズム

START
   Step 1 -> create node variable of type structure
      Declare int data
      Declare pointer of type node using *next
   Step 2 -> Declare function as node* get(int data)
      Create newnode using malloc function
      Set newnode->data = data
      Set newnode->next = NULL
      return newnode
   step 3 -> Declare function void lastval(node* head, int& count, int k)
      IF !head
         Return
      Set lastval(head->next, count, k)
      Set count++
      IF (count <= k)
         Print head->data
   Step 4 -> In Main()
      Generate head using node* head = get(11)
      Set k and count to 0
      Call lastval(head,k,count)
STOP

例

#include<stdio.h>
#include<stdlib.h>
// Structure of a node
struct node {
   int data;
   node* next;
};
// Function to get a new node
node* get(int data) {
   struct node* newnode = (struct node*)malloc(sizeof(struct node));
   newnode->data = data;
   newnode->next = NULL;
   return newnode;
}
//print the last k values of a node
void lastval(node* head, int& count, int k) {
   if (!head)
      return;
   lastval(head->next, count, k);
   count++;
   if (count <= k)
      printf("%d ", head->data);
}
int main() {
   node* head = get(11); //inserting elements into the list
   head->next = get(243);
   head->next->next = get(321);
   head->next->next->next = get(421);
   head->next->next->next->next = get(522);
   int k = 2, count = 0;
   printf(" last %d nodes of a list are :",k);
   // print last k nodes
   lastval(head, count, k);
   return 0;
}

出力

上記のプログラムを実行すると、次の出力が生成されます。

last 2 nodes of a list are :522 421