C++程序查找两个有序链表的交集

在C++中，链表是一种非常常用的数据结构。很多情况下，我们需要通过比对两个链表来寻找它们的交集。本文将介绍如何在C++程序中查找两个有序链表的交集。

需求分析

假设我们有两个有序链表L1和L2，它们的元素类型均为整数，我们需要找到它们的交集。具体来说，就是要从L1和L2中找到所有在两者中都出现的数字，并将它们储存到一个新的链表中。

为了简化问题，我们假设L1和L2的长度分别为S1和S2，其中S1 <= S2。同时，我们假设程序运行时间是有限制的。也就是说，我们需要设计一个时间复杂度尽可能低的算法。

解法设计

最简单的方法是遍历L1中的每个元素，并在L2中查找是否存在相同的元素。这样做的时间复杂度为O(S1*S2)，但显然这个方案的效率太低。

因此，我们需要寻找一种时间复杂度更低的解法。我们可以发现，由于L1和L2是有序的，因此当我们遍历L1时，可以根据当前元素的大小，确定在L2中需要查找哪些元素。

具体来说，我们维护两个指针p和q，分别指向L1和L2的头结点。我们同时遍历L1和L2。如果当前p所指的节点的元素值小于q所指节点的元素值，则p向后移动一位；如果p所指节点的值大于q所指节点的值，则q向后移动一位。如果相等，则将该元素储存到交集中，p和q同时后移一位。

虽然这种解法用到了两个指针，但由于p和q所指的节点都是递增的，因此解法的时间复杂度为O(S1+S2)，可以满足对算法运行时间有限制的需求。

代码实现

下面是该算法的具体实现：

#include<iostream>
#include<cstdlib>

using namespace std;

struct Node {   //链表节点的结构体
    int val;
    Node *next;
    Node(int x) : val(x), next(NULL) {}
};

class Solution {   //定义一个解决方案的类
public:
    Node* getIntersection(Node* headA, Node* headB) {
        if(headA == NULL || headB == NULL)
            return NULL;
        Node* p = headA,* q = headB, * res = NULL;  //res表示交集链表
        while(p != NULL && q != NULL) {
            if(p -> val < q -> val)
                p = p -> next;
            else if(q -> val < p -> val)
                q = q -> next;
            else {
                if(res == NULL)
                    res = new Node(p -> val);
                else {
                    Node* temp = res;
                    while(temp -> next != NULL)
                        temp = temp -> next;
                    temp -> next = new Node(p -> val);
                }
                p = p -> next; q = q -> next;
            }
        }
        return res;
    }
};

测试样例

下面是对上面所写程序的一组测试样例：

int main() {
    Node* n1 = new Node(1); 
    Node* n2 = new Node(2);
    Node* n3 = new Node(3);
    Node* n4 = new Node(4);
    Node* n5 = new Node(5);

    n1 -> next = n2;
    n2 -> next = n3;
    n3 -> next = n4;
    n4 -> next = n5;

    Node* m1 = new Node(2);
    Node* m2 = new Node(4);
    Node* m3 = new Node(5);

    m1 -> next = m2;
    m2 -> next = m3;

    Solution solution;
    Node* res = solution.getIntersection(n1,m1);
    while(res != NULL) {
        cout << res -> val << " ";
        res = res -> next;
    }
    cout << endl;

    return 0;
}

输出结果为：