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

给定两个按递增顺序排序的链表，创建并返回表示两个列表交集的新列表。新列表应使用自己的内存——原始列表不应更改。

例如：

输入：
第一个链表：1->2->3->4->6
第二个链表：2->4->6->8，
输出： 2->4->6。
元素2、4、6在两个列表中均为共同元素，因此它们出现在交集列表中。

输入：
第一个链表：1->2->3->4->5
第二个链表：2->3->4，
输出： 2->3->4
元素2、3、4在两个列表中均为共同元素，因此它们出现在交集列表中。

方法1： 使用虚拟节点。

实现：

这个方法的思路是在结果列表的开头使用一个临时的虚拟节点。指针tail始终指向结果列表中的最后一个节点，因此可以很容易地添加新节点。虚拟节点最初给tail分配内存空间。这个虚拟节点效率很高，因为它只是临时的，并且它是在stack中分配的。循环过程中，从a或b中删除一个节点，并将其添加到tail中。当给定的列表遍历完成后，结果存储在dummy.next中，因为值从dummy的下一个节点分配。如果两个元素相等，则删除它们并将元素插入到tail中。否则，移除两个列表中元素较小的那个。

以下是上述方法的实现：

#include<bits/stdc++.h>
using namespace std;
 
// 链表结点
struct Node
{
    int data;
    Node* next;
};
 
// 在链表头插入新节点
void push(Node** head_ref,
          int new_data);
 
/* 此解决方案使用临时的dummy来构建结果链表 */
Node* sortedIntersect(Node* a, Node* b)
{
    Node dummy;
    Node* tail = &dummy
    dummy.next = NULL;
 
    /* 一旦其中一个链表用完了 - 我们就完成了 */
    while (a != NULL && b != NULL)
    {
        if (a->data == b->data)
        {
            push((&tail->next), a->data);
            tail = tail->next;
            a = a->next;
            b = b->next;
        }
        // 推进较小的链表
        else if (a->data < b->data)
            a = a->next;
        else
            b = b->next;
    }
    return (dummy.next);
}
 
// 工具函数
/* 在链表头插入新节点 */
void push(Node** head_ref, int new_data)
{
    // 分配节点
    Node* new_node =
          (Node*)malloc(sizeof(Node));
 
    // 放入数据
    new_node->data = new_data;
 
    // 链接新节点的旧链表
    new_node->next = (*head_ref);
 
    // 移动头指针到新节点
    (*head_ref) = new_node;
}
 
/* 打印给定链表中的结点 */
void printList(Node* node)
{
    while (node != NULL)
    {
        cout << node->data <<" ";
        node = node->next;
    }
}
 
// 主函数
int main()
{
    // 从空链表开始
    Node* a = NULL;
    Node* b = NULL;
    Node* intersect = NULL;
 
    /* 创建第一个排序链表以测试函数
      创建的排序链表将是
      1->2->3->4->5->6 */
    push(&a, 6);
    push(&a, 5);
    push(&a, 4);
    push(&a, 3);
    push(&a, 2);
    push(&a, 1);
 
    /* 创建第二个排序链表，创建链表为
      2->4->6->8 */
    push(&b, 8);
    push(&b, 6);
    push(&b, 4);
    push(&b, 2);
 
    // 找到两个链表的交集
    intersect = sortedIntersect(a, b);
 
    cout <<
    "Linked list containing common items of a & b ";
    printList(intersect);
}  

输出:

Linked list containing common items of a & b 
2 4 6 

复杂度分析:

• 时间复杂度: O(m+n)，其中m和n分别为第一个和第二个链表中的节点数。 只需要对列表进行一次遍历。
• 辅助空间: O(min(m, n))。 输出列表最多可以存储min(m,n)个结点。

方法2： 递归解法。

方法:

递归的方法与以上两种方法非常相似。构建一个递归函数，该函数将两个节点作为参数并返回一个链接列表节点。比较两个链表的第一个元素。

• 如果它们相同，则将递归函数与两个链表的下一个节点一起调用。创建一个带有当前节点数据的节点，并将递归函数返回的节点放入创建的节点的下一个指针中。返回创建的节点。
• 如果两者的值不相等，则删除两个链表中较小的节点并调用递归函数。

下面是上述方法的实现:

// C++程序实现
// 上述方法
#include <bits/stdc++.h>
using namespace std;
 
// 链表节点
struct Node
{
    int data;
    struct Node* next;
};
 
struct Node* sortedIntersect(struct Node* a,
                              struct Node* b)
{   
    // 基本情况
    if (a == NULL || b == NULL)
        return NULL;
 
    // 如果两个列表都不为空
 
    /* 推进更小的列表并
       递归调用 */
    if (a->data < b->data)
        return sortedIntersect(a->next, b);
 
    if (a->data > b->data)
        return sortedIntersect(a, b->next);
 
    // 仅在a->data == b->data时执行下面的行
    struct Node* temp =
           (struct Node*)malloc(sizeof(struct Node));
    temp->data = a->data;
 
    // 推进两个列表并递归调用
    temp->next = sortedIntersect(a->next,
                                    b->next);
    return temp;
}
 
// UTILITY FUNCTIONS
/* 在链表开头插入一个节点的函数 */
void push(struct Node** head_ref,
              int new_data)
{   
    // 分配节点
    struct Node* new_node =
           (struct Node*)malloc(sizeof(struct Node));
 
    // 输入数据
    new_node->data = new_data;
 
    // 链接新节点的旧列表
    new_node->next = (*head_ref);
 
    // 将头部移动到指向新节点
    (*head_ref) = new_node;
}
 
/* 在给定链表中打印节点的函数 */
void printList(struct Node* node)
{
    while (node != NULL)
    {
        cout << " " << node->data;
        node = node->next;
    }
}
 
// Driver Code
int main()
{   
    // 从空列表开始
    struct Node* a = NULL;
    struct Node* b = NULL;
    struct Node* intersect = NULL;
 
    /* 创建第一个排序的链表以测试函数
       创建的链接列表将是
       1->2->3->4->5->6 */
    push(&a, 6);
    push(&a, 5);
    push(&a, 4);
    push(&a, 3);
    push(&a, 2);
    push(&a, 1);
 
    /* 创建第二个排序的链表。创建的链接列表
       将是2->4->6->8 */
    push(&b, 8);
    push(&b, 6);
    push(&b, 4);
    push(&b, 2);
 
    // 查找两个链接列表的交集
    intersect = sortedIntersect(a, b);
 
    cout << "Linked list containing " <<
                "common items of a & b ";
    printList(intersect);
 
    return 0;
}
// 此代码由shivanisinghss2110贡献```  

输出：

Linked list containing common items of a & b 
2 4 6

复杂度分析：

• 时间复杂度： O(m+n)，其中m和n分别是第一个链表和第二个链表中的节点数。 只需要遍历一次列表。
• 辅助空间： O(max(m, n))。 输出列表至多可以存储m+n个节点。