C++程序找到三个链表中和等于给定数字的三元组

给定三个链表a、b和c，找到每个链表中的一个节点，使得这些节点的值的和等于给定的数字。

例如，如果三个链表分别为12->6->29、23->5->8和90->20->59，给定数字为101，则输出应为“6 5 90”。

在以下解决方案中，为了简化分析，假设所有三个链表的大小相同。以下解决方案也适用于不同大小的链表。

解决这个问题的一个简单方法是运行三个嵌套循环。外层循环从列表a中选择一个元素，中间循环从列表b中选择一个元素，内部循环从列表c中选择一个元素。内部循环还会检查a、b和c的当前节点的值的总和是否等于给定的数字。这种方法的时间复杂度将是O(n^3)。

为了将时间复杂度降至O(n*n)，可以使用排序。以下是详细步骤。

1）将列表b按升序排序，将列表c按降序排序。

2）在排序b和c之后，逐一从列表a中选择一个元素，并通过遍历b和c找到该元素的配对。请参阅以下代码中的isSumSorted()。这个想法类似于3 sum问题的二次算法。

以下代码仅实现步骤2。可以通过添加合并排序代码在非排序的列表上轻松修改解决方案。

// C++程序，找到三个链表中的一个三元组，使它们的和等于给定的数字
#include <bits/stdc++.h>
using namespace std;
 
/* 链表节点 */
class Node
{
    public:
    int data;
    Node* next;
};
 
/* 在链表开始处插入一个节点的函数 */
void push (Node** head_ref, int new_data)
{
    /* 分配一个新节点 */
    Node* new_node = new Node();
 
    /* 添加数据 */
    new_node->data = new_data;
 
    /* 来连接新节点的旧链表 */
    new_node->next = (*head_ref);
 
    /* 将头移动到新结点 */
    (*head_ref) = new_node;
}
 
/* 一个函数来检查a、b和c中是否有三个元素的总和等于给定的数字。这个函数假设列表b按升序排序，c按降序排序。 */
bool isSumSorted(Node *headA, Node *headB,
                Node *headC, int givenNumber)
{
    Node *a = headA;
 
    // 遍历所有a的节点
    while (a != NULL)
    {
        Node *b = headB;
        Node *c = headC;
 
        // 对于列表a的每个结点，从列表b和c中逐个挑选两个结点
        while (b != NULL && c != NULL)
        {
            // 如果这是一个具有给定总和的三元组，则打印它并返回true
            int sum = a->data + b->data + c->data;
            if (sum == givenNumber)
            {
            cout << "Triplet Found: " << a->data << " " <<
                                b->data << " " << c->data;
            return true;
            }
 
            // 如果这个三元组的总和更小，则在b中寻找更大的值
            else if (sum < givenNumber)
                b = b->next;
            else // 如果这个sum更大，则在c中寻找更小的值
                c = c->next;
        }
        a = a->next; // 在列表a中继续往后移动
    }
 
    cout << "No such triplet";
    return false;
}
 
 
/* 主函数*/
int main()
{
    /* 开始一个空链表 */
    Node* headA = NULL;
    Node* headB = NULL;
    Node* headC = NULL;
 
    /*创建一个链表'a'，10 → 15 → 5 → 20 */
    push (&headA, 20);
    push (&headA, 4);
    push (&headA, 15);
    push (&headA, 10);
 
    /*创建一个已排序的链表'b'，2 → 4 → 9 → 10 */
    push (&headB, 10);
    push (&headB, 9);
    push (&headB, 4);
    push (&headB, 2);
 
    /*创建另一个已排序的
    链表'c'，8 → 4 → 2 → 1 */
    push (&headC, 1);
    push (&headC, 2);
    push (&headC, 4);
    push (&headC, 8);
 
    int givenNumber = 25;
 
    isSumSorted (headA, headB, headC, givenNumber);
 
    return 0;
}
 
// 该代码由rathbhupendra贡献```