Danh sách được liên kết là cấu trúc dữ liệu tuyến tính trong đó mỗi nút có hai khối sao cho một khối chứa giá trị hoặc dữ liệu của nút và khối còn lại chứa địa chỉ của trường tiếp theo.
Giả sử rằng chúng ta có một danh sách được liên kết sao cho mỗi nút chứa một con trỏ ngẫu nhiên trỏ đến các nút khác trong danh sách. Nhiệm vụ là tìm nút mà tại đó hai danh sách liên kết giao nhau. Nếu chúng không giao nhau, thì trả về NULL hoặc rỗng làm đầu ra.
Ví dụ
Đầu vào-1:
Đầu ra:
2
Giải thích: Vì danh sách được liên kết đã cho giao nhau tại nút có giá trị '2', chúng tôi sẽ trả về giá trị '2' làm đầu ra.
Đầu vào-2:
Đầu ra:
NULL
Giải thích: Vì không có điểm chung, chúng tôi sẽ trả về NULL trong trường hợp này.
Phương pháp tiếp cận để giải quyết vấn đề này
Chúng tôi có hai danh sách được liên kết với một điểm chung là chúng giao nhau. Để tìm giao điểm, chúng tôi sẽ duyệt qua cả hai danh sách được liên kết cho đến khi chúng tôi thấy rằng chúng đều trỏ đến cùng một giá trị. Tại một số điểm, con trỏ đến nút tiếp theo của danh sách liên kết sẽ giống nhau. Do đó, chúng tôi sẽ trả về giá trị của điểm đó.
- Lấy hai danh sách được liên kết với dữ liệu và con trỏ đến nút tiếp theo.
- Một hàm commonPoint (listnode * headA, listnode * headB) nhận hai con trỏ của danh sách được liên kết và trả về giá trị của điểm chung hoặc điểm giao của danh sách được liên kết.
- Một hàm số nguyên tìm độ dài của danh sách được liên kết sẽ trả về độ dài của cả hai danh sách được liên kết từ phần đầu của danh sách.
- Bây giờ, hãy tạo một con trỏ đến đầu của cả hai danh sách và duyệt qua danh sách có độ dài lớn hơn cho đến (độ dài của danh sách đầu tiên - độ dài của danh sách thứ hai).
- Bây giờ xem qua danh sách cho đến khi chúng tôi tìm thấy con trỏ tiếp theo bằng nhau.
- Trả lại giá trị của nút cụ thể nơi cả hai danh sách giao nhau.
Ví dụ
#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;
} Chạy đoạn mã trên sẽ tạo ra kết quả là,
Đầu ra
7
Giải thích: Các danh sách được liên kết đã cho đang hợp nhất tại '7'.
