In k nút cuối cùng của danh sách liên kết theo thứ tự ngược lại Cách tiếp cận lặp lại trong ngôn ngữ C

Chúng ta phải in ra k số nút của danh sách liên kết theo thứ tự ngược lại. Chúng tôi phải áp dụng phương pháp lặp đi lặp lại để giải quyết vấn đề này.

Phương thức lặp là phương thức thường sử dụng các vòng lặp được thực thi cho đến khi điều kiện giữ giá trị 1 hoặc true.

Giả sử, danh sách chứa các nút 29, 34, 43, 56 và 88 và giá trị của k lớn hơn 2 so với đầu ra sẽ là các nút thay thế cho đến k chẳng hạn như 56 và 88.

Ví dụ

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

Vì chúng ta phải xóa k phần tử cuối cùng khỏi danh sách nên cách tốt nhất để làm là sử dụng cấu trúc dữ liệu ngăn xếp trong đó các phần tử được đẩy sẽ tạo ra danh sách và các phần tử bắt đầu của ngăn xếp là phần tử cuối cùng của danh sách và chúng bật ra từ ngăn xếp cho đến số lần thứ k cho chúng ta các nút cuối cùng của danh sách được liên kết.

Đoạn mã dưới đây cho thấy cách triển khai c của thuật toán đã cho.

Thuật toán

START
   Step 1 -> create node variable of type structure
      Declare int data
      Declare pointer of type node using *next
   Step 2 -> create struct node* intoList(int data)
      Create newnode using malloc
      Set newnode->data = data
      newnode->next = NULL
      return newnode
   step 3 -> Declare function void rev(struct node* head,int count, int k)
      create struct node* temp1 = head
      Loop While(temp1 != NULL)
         count++
         temp1 = temp1->next
      end
      Declare int array[count], temp2 = count,i
      Set temp1 = head
      Loop While(temp1 != NULL)
         Set array[--temp2] = temp1->data
         Set temp1 = temp1->next
      End
      Loop For i = 0 and i < k and i++
         Print array[i]
      End
   Step 4 -> In Main()
      Create list using struct node* head = intoList(9)
      Set k=3 and count=0
      Call rev(head,count,k)
STOP

Ví dụ

#include<stdio.h>
#include<stdlib.h>
// Structure of a node
struct node {
   int data;
   struct node *next;
};
//functon for inserting a new node
struct node* intoList(int data) {
   struct node* newnode = (struct node*)malloc(sizeof(struct node));
   newnode->data = data;
   newnode->next = NULL;
   return newnode;
}
// Function to reversely printing the elements of a node
void rev(struct node* head,int count, int k) {
   struct node* temp1 = head;
   while(temp1 != NULL) {
      count++;
      temp1 = temp1->next;
   }
   int array[count], temp2 = count,i;
   temp1 = head;
   while(temp1 != NULL) {
      array[--temp2] = temp1->data;
      temp1 = temp1->next;
   }
   for(i = 0; i < k; i++)
   printf("%d ",array[i]);
}
int main() {
   printf("\nreverse of a list is : ");
   struct node* head = intoList(9); //inserting elements into a list
   head->next = intoList(76);
   head->next->next = intoList(13);
   head->next->next->next = intoList(24);
   head->next->next->next->next = intoList(55);
   head->next->next->next->next->next = intoList(109);
   int k = 3, count = 0;
   rev(head, count, k); //calling function to print reversely
   return 0;
}

Đầu ra

Nếu chúng ta chạy chương trình trên thì nó sẽ tạo ra kết quả sau.

reverse of a list is : 109 55 24