รายการที่เชื่อมโยงเป็นโครงสร้างข้อมูลเชิงเส้นซึ่งแต่ละโหนดมีสองบล็อก โดยที่หนึ่งบล็อกมีค่าหรือข้อมูลของโหนด และอีกบล็อกหนึ่งมีที่อยู่ของฟิลด์ถัดไป
สมมติว่าเรามีรายการที่เชื่อมโยง โดยที่แต่ละโหนดมีตัวชี้สุ่มซึ่งชี้ไปยังโหนดอื่นในรายการ ภารกิจคือการค้นหาโหนดที่รายการที่เชื่อมโยงสองรายการตัดกัน หากไม่ตัดกัน ให้คืนค่า NULL หรือค่าว่างเป็นเอาต์พุต
ตัวอย่าง
อินพุต-1:
ผลลัพธ์:
2
คำอธิบาย: เนื่องจากรายการเชื่อมโยงที่กำหนดตัดกันที่โหนดด้วยค่า '2' เราจะคืนค่า '2' เป็นผลลัพธ์
อินพุต-2:
ผลลัพธ์:
NULL
คำอธิบาย: เนื่องจากไม่มีจุดร่วม เราจะคืนค่า NULL ในกรณีนี้
แนวทางในการแก้ปัญหานี้
เรามีรายการที่เชื่อมโยงสองรายการที่มีจุดร่วมที่พวกมันตัดกัน ในการหาจุดตัด เราจะสำรวจทั้งสองรายการที่เชื่อมโยงจนพบว่าชี้ไปที่ค่าเดียวกันเท่ากัน ในบางจุด ตัวชี้ไปยังโหนดถัดไปของรายการที่เชื่อมโยงจะเหมือนเดิม ดังนั้นเราจะคืนค่าของจุดนั้น
- นำรายการที่เชื่อมโยงสองรายการพร้อมข้อมูลและตัวชี้ไปยังโหนดถัดไป
- ฟังก์ชัน commonPoint(listnode*headA, listnode*headB) รับตัวชี้สองตัวของรายการที่เชื่อมโยงตามลำดับและส่งกลับค่าของจุดร่วมหรือจุดตัดของรายการที่เชื่อมโยง
- ฟังก์ชันจำนวนเต็มที่ค้นหาความยาวของรายการที่เชื่อมโยงจะคืนค่าความยาวของรายการที่เชื่อมโยงทั้งสองจากส่วนหัวของรายการ
- ตอนนี้สร้างตัวชี้ไปที่ส่วนหัวของทั้งสองรายการและสำรวจรายการซึ่งมีความยาวมากกว่าจนถึง (ความยาวของรายการแรก – ความยาวของรายการที่สอง)
- ตอนนี้สำรวจรายการจนกว่าเราจะพบว่าตัวชี้ถัดไปเท่ากัน
- คืนค่าของโหนดเฉพาะที่รายการทั้งสองตัดกัน
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class listnode {
public:
int data;
listnode * next;
};
// Find the length of the linked list
int count(listnode * head) {
int count = 0;
while (head != NULL) {
count++;
head = head -> next;
}
return count;
}
//Function to get the common point of two linked list
int commonPoint(listnode * headA, listnode * headB) {
int len1 = count(headA);
int len2 = count(headB);
listnode * p1 = headA;
listnode * p2 = headB;
if (len1 > len2) {
for (int i = 0; i < len1 - len2; ++i) {
p1 = p1 -> next;
}
}
if (len1 < len2) {
for (int i = 0; i < len2 - len1; ++i) {
p2 = p2 -> next;
}
}
while (p1 != NULL and p2 != NULL) {
if (p1 == p2) {
return p1 -> data;
}
p1 = p1 -> next;
p2 = p2 -> next;
}
return -1;
}
int main() {
listnode * head;
listnode * headA = new listnode();
headA -> data = 5;
listnode * headB = new listnode();
headB -> data = 4;
head = new listnode();
head -> data = 9;
headB -> next = head;
head = new listnode();
head -> data = 2;
headB -> next -> next = head;
head = new listnode();
head -> data = 7;
headA -> next = head;
headB -> next -> next -> next = head;
head = new listnode();
head -> data = 3;
headA -> next -> next = head;
headA -> next -> next -> next = NULL;
cout << commonPoint(headA, headB) << endl;
} การเรียกใช้โค้ดด้านบนจะสร้างผลลัพธ์เป็น
ผลลัพธ์
7
คำอธิบาย: รายการเชื่อมโยงที่กำหนดกำลังรวมกันที่ '7'
