Khái niệm
Đối với một danh sách liên kết đôi được sắp xếp đã cho gồm các phần tử khác biệt dương, nhiệm vụ của chúng tôi là xác định các cặp trong danh sách được liên kết đôi có tích của chúng bằng giá trị x đã cho mà không tốn thêm dung lượng.
Đầu vào
List = 1 <=> 2 <=> 4 <=> 5 <=> 6 <=> 8 <=> 9 x = 8
Đầu ra
(1, 8), (2, 4)
Đầu vào
List1 = 1 <=> 2 <=> 3 <=> 4 <=> 5 <=> 6 <=> 7 x = 6
Đầu ra
(1, 4), (2,3)
Phương pháp
Theo Cách tiếp cận đơn giản đối với vấn đề này, chúng tôi duyệt qua danh sách được liên kết thực hiện hai vòng lặp lồng nhau và xác định tất cả các cặp và xác minh các cặp có tích bằng x. Ở đây, độ phức tạp về thời gian cho vấn đề này sẽ là O (n ^ 2), trong đó n là tổng số nút trong danh sách liên kết kép.
Giải pháp hiệu quả cho vấn đề này được thảo luận. Đây là các bước của thuật toán -
Chúng tôi khởi tạo hai biến con trỏ để xác định các phần tử ứng cử viên trong danh sách liên kết kép đã được sắp xếp.
Chúng tôi khởi tạo first1 với đầu danh sách được liên kết kép có nghĩa là, first1 =head và khởi tạo second1 với nút cuối cùng của danh sách được liên kết kép có nghĩa là, second1 =last_node.
Bây giờ chúng ta khởi tạo con trỏ đầu tiên và thứ hai làm nút đầu tiên và nút cuối cùng. Trong trường hợp này, chúng tôi không có quyền truy cậprandom, vì vậy, để xác định con trỏ thứ hai, chúng tôi truy cập danh sách để khởi chạy second1.
Người ta đã thấy rằng nếu tổng hiện tại của thứ nhất1 và thứ hai nhỏ hơn x, thì chúng ta di chuyển đầu tiên1 theo hướng thuận. Ngược lại, nếu tổng hiện tại của giây thứ nhất và thứ nhất lớn hơn x, thì chúng ta sẽ di chuyển giây thứ nhất theo hướng ngược lại.
Cuối cùng, các điều kiện kết thúc vòng lặp cũng khác với mảng. Trong trường hợp này, vòng lặp kết thúc khi một trong hai con trỏ trở thành NULL hoặc chúng giao nhau (second1-> next =first1) hoặc chúng giống nhau (first1 ==second1).
Ví dụ
// C++ program to find a pair with
// given product x in sorted Doubly
// Linked List
#include <bits/stdc++.h>
using namespace std;
//Shows Doubly Linked List Node
struct Node1 {
int data1;
struct Node1 *next1, *prev1;
};
// Shows function to determine pair whose product
// equal to given value x
void pairProduct(struct Node1* head1, int x1){
// Now set two pointers,
// first to the beginning of DLL and second to the end of DLL.
struct Node1* first1 = head1;
struct Node1* second1 = head1;
while (second1->next1 != NULL)
second1 = second1->next1;
// Used to track if we find a pair or not
bool found1 = false;
// Now the loop terminates when either of two pointers
// become NULL, or they cross each other (second1->next1
// == first1), or they become same (first1 == second1)
while (first1 != NULL && second1 != NULL && first1 != second1 && second1->next1 != first1) {
// pair found
if ((first1->data1 * second1->data1) == x1) {
found1 = true;
cout << "(" << first1->data1 << ", " << second1->data1 << ")" << endl;
// Used to move first in forward direction
first1 = first1->next1;
// Used to move second in backward direction
second1 = second1->prev1;
} else {
if ((first1->data1 * second1->data1) < x1)
first1 = first1->next1;
else
second1 = second1->prev1;
}
}
// Now if pair is not present
if (found1 == false)
cout << "No pair found";
}
// Shows a utility function to insert a new node at the
// beginning of doubly linked list
void insert(struct Node1** head1, int data1){
struct Node1* temp1 = new Node1;
temp1->data1 = data1;
temp1->next1 = temp1->prev1 = NULL;
if (!(*head1))
(*head1) = temp1;
else {
temp1->next1 = *head1;
(*head1)->prev1 = temp1;
(*head1) = temp1;
}
}
// Driver Code
int main(){
// Create Doubly Linked List struct Node1* head1 = NULL;
/*insert(&head1, 9);
insert(&head1, 8);
insert(&head1, 6);
insert(&head1, 5);
insert(&head1, 4);
insert(&head1, 2);
insert(&head1, 1);
int x1 = 8; */
insert(&head1, 7);
insert(&head1, 6);
insert(&head1, 5);
insert(&head1, 4);
insert(&head1, 3);
insert(&head1, 2);
insert(&head1, 1);
int x1 = 6;
pairProduct(head1, x1);
return 0;
} Đầu ra
(1, 6) (2, 3)