รายการที่เชื่อมโยงเป็นโครงสร้างข้อมูลเชิงเส้นที่มีหลายโหนดที่เชื่อมต่อถึงกัน แต่ละโหนดประกอบด้วยสองฟิลด์ ฟิลด์ข้อมูล และที่อยู่ของโหนดถัดไป สมมติว่าเราได้ให้รายการที่เชื่อมโยงโดยลำพัง ภารกิจคือการค้นหาโหนด kth จากจุดสิ้นสุดในรายการที่เชื่อมโยงโดยลำพัง ตัวอย่างเช่น
ป้อนข้อมูล −
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) นำตัวชี้ไปยังโหนดหลักและตำแหน่งเป็นพารามิเตอร์และส่งกลับโหนดจากจุดสิ้นสุด
-
ลองใช้ตัวชี้สองตัวที่ "ช้า" และ "เร็ว" ซึ่งเริ่มแรกอยู่ที่หัว
-
วนซ้ำในรายการที่เชื่อมโยงและเลื่อนตัวชี้แบบเร็ว
-
เนื่องจากตัวชี้ "เร็ว" นั้นนำหน้า "ช้า" อยู่ 2 ก้าว ให้เราเลื่อนตัวชี้ทั้งสองไปจนกว่า "เร็ว" จะถึงจุดสิ้นสุด
-
ตอนนี้คืนค่าที่ช้าซึ่งชี้ไปที่โหนด 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→ และค่า kth คือ '4' ดังนั้นโหนดที่ 4 จากจุดสิ้นสุดคือ '6' ดังนั้นเราจะส่งคืน '6'
