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

在C++程序中，我们常常需要操作链表数据结构。其中，找到三个链表中和等于给定数字的三元组是一种常见的问题。本文将介绍如何在C++程序中实现这一功能。

题目描述

给定三个升序排列的链表，以及一个数字target，从中找到三个元素a，b，c，使得它们的和等于target。并返回所有这样的三元组。

例如，如果给定链表1：1->2->3->4，链表2：2->3->4->5，链表3：4->5->6->7，target：9，那么返回的三元组应该是（1，2，6）、（1，3，5）和（2，2，5）。

思路

一般的思路是固定其中一个链表的值，然后对另外两个链表采用双指针法，逐个枚举三个数的组合，进行判断。具体步骤如下：

遍历第一个链表，对于每一个节点都从第二个链表的最左侧开始和第三个链表的最右侧开始双指针遍历。
对于第二个链表和第三个链表，设置两个指针left和right，分别指向链表的头节点和尾节点。
在left小于right的条件下，判断当前三个数的和是否等于target。若等于，记录三元组，并将left指针往右移，right指针往左移；否则，若和小于target，则left往右移；若和大于target，则right往左移。
遍历完第一个链表后，按升序返回所有记录的三元组。

代码实现

下面是代码实现，首先定义了一个ListNode结构体用于表示链表节点：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

接下来，是实现找出给定三个链表中和为目标值的三元组的函数：

vector<vector<int>> threeSum(ListNode* l1, ListNode* l2, ListNode* l3, int target) {
    vector<vector<int>> res; // 结果数组
    vector<int> cur(3, 0); // 当前得到的三元组

    ListNode* p1 = l1; // 遍历第一个链表
    while (p1) {
        ListNode* left = l2; // 第二个链表的左指针
        ListNode* right = l3; // 第三个链表的右指针

        while (left && right) { // 双指针遍历第二个、第三个链表
            int sum = p1->val + left->val + right->val; // 计算三数之和

            if (sum == target) { // 如果等于目标值，记录此三元组，并更新left和right
                cur[0] = p1->val;
                cur[1] = left->val;
                cur[2] = right->val;
                res.push_back(cur);

                left = left->next; // left指针右移
                right = right->next; // right指针左移
            } else if (sum < target) { // 如果小于目标值，left指针右移
                left = left->next;
            } else { // 如果大于目标值，right指针左移
                right = right->next;
            }
        }

        p1 = p1->next; // 第一个链表指针右移
    }

    sort(res.begin(), res.end()); // 升序排列结果数组
    res.erase(unique(res.begin(), res.end()), res.end()); // 去除重复结果

    return res;
}

完整代码

下面是完整的程序代码：

```C++
# include <iostream>
# include <vector>
# include <algorithm>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

vector<vector<int>> threeSum(ListNode* l1, ListNode* l2, ListNode* l3, int target) {
    vector<vector<int>> res;
    vector<int> cur(3, 0);

    ListNode* p1 = l1;
    while (p1) {
        ListNode* left = l2;
        ListNode* right = l3;

        while (left && right) {
            int sum = p1->val + left->val + right->val;

            if (sum == target) {
                cur[0] = p1->val;
                cur[1] = left->val;
                cur[2] = right->val;
                res.push_back(cur);

                left = left->next;
                right = right->next;
            } else if (sum < target) {
                left = left->next;
            } else {
                right = right->next;
            }
        }

        p1 = p1->next;
    }

    sort(res.begin(), res.end());
    res.erase(unique(res.begin(), res.end()), res.end());

    return res;
}

int main() {
    ListNode* l1 = new ListNode(1);
    l1->next = new ListNode(2);
    l1->next->next = new ListNode(3);
    l1->next->next->next = new ListNode(4);

    ListNode* l2 = new ListNode(2);
    l2->next = new ListNode(3);
    l2->next->next = new ListNode(4);
    l2->next->next->next = new ListNode(5);

    ListNode* l3 = new ListNode(4);
    l3->next = new ListNode(5);
    l3->next->next = new ListNode(6);
    l3->next->next->next = new ListNode(7);

    int target = 9;

    vector<vector<int>> res = threeSum(l1, l2, l3, target);

    for (auto triple : res) {
        cout << "(" << triple[0] << ", " << triple[1] << ", " << triple[2] << ")" << endl;
    }

    return 0;
}