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'입니다. 따라서 끝에서 네 번째 노드는 '6'이므로 '6'을 반환합니다.