Tìm Nút thứ K từ cuối trong một Danh sách được liên kết đơn lẻ nhất định bằng C ++

Danh sách liên kết là một cấu trúc dữ liệu tuyến tính có nhiều nút được kết nối với nhau. Mỗi nút bao gồm hai trường Trường dữ liệu và địa chỉ của nút tiếp theo. Giả sử chúng ta đã đưa ra một danh sách liên kết đơn, nhiệm vụ là tìm nút thứ k từ cuối trong một danh sách liên kết đơn nhất định. Ví dụ:

Đầu vào -

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

Đầu ra -

Node from the 4th Position is − 4

Giải thích - Vì trong danh sách liên kết đơn đã cho nút ‘thứ 4’ từ cuối là ‘4’, chúng tôi sẽ trả về đầu ra là ‘4’.

Phương pháp tiếp cận để giải quyết vấn đề này

Ban đầu, chúng tôi đã đưa ra một danh sách liên kết bao gồm các nút. Mỗi nút chứa dữ liệu và địa chỉ đến nút tiếp theo. Vì vậy, để tìm nút thứ k từ cuối, chúng ta sẽ lấy hai con trỏ trỏ đến phần đầu của danh sách được liên kết.

Trong khi lặp lại danh sách được liên kết, chúng tôi sẽ di chuyển một trong các con trỏ, giả sử là "nhanh", rồi di chuyển con trỏ khác cho đến khi con trỏ "nhanh" không đến cuối.

• Hàm kthNodefromTheEnd (node ​​* head, int pos) đưa con trỏ đến nút đầu và vị trí làm tham số và trả về nút từ cuối.

• Hãy lấy hai con trỏ "chậm" và "nhanh" ban đầu ở đầu.

• Lặp lại danh sách được liên kết và di chuyển con trỏ nhanh.

• Vì con trỏ "nhanh" đi trước hai bước so với "chậm", nên chúng tôi di chuyển cả hai con trỏ cho đến khi kết thúc "nhanh".

• Bây giờ trả về giá trị chậm trỏ đến nút thứ k từ cuối.

Ví dụ

#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;
}

Đầu ra

Chạy đoạn mã trên sẽ tạo ra kết quả là,

Node from the 4th position is: 6

Giải thích - Danh sách liên kết đã cho là 7 → 6 → 5 → 4 → 2 → và giá trị thứ k là ‘4’. Vì vậy, nút thứ 4 từ cuối là "6", do đó chúng tôi sẽ trả về "6".