当前位置：极客教程 > C++语言 > C++ 示例 > C++程序 查找两个有序链表的交集

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

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);
}
C++

输出:

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

复杂度分析:

  • 时间复杂度: 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贡献```
C++

输出：

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

复杂度分析：

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

Python教程

Python 教程

Python 教程
Tkinter 教程

Tkinter 教程
Pandas 教程

Pandas 教程
NumPy 教程

NumPy 教程
Flask 教程

Flask 教程
Django 教程

Django 教程
PySpark 教程

PySpark 教程
wxPython 教程

wxPython 教程
SymPy 教程

SymPy 教程
Seaborn 教程

Seaborn 教程
SciPy 教程

SciPy 教程
RxPY 教程

RxPY 教程
Pycharm 教程

Pycharm 教程
Pygame 教程

Pygame 教程
PyGTK 教程

PyGTK 教程
PyQt 教程

PyQt 教程
PyQt5 教程

PyQt5 教程
PyTorch 教程

PyTorch 教程
Matplotlib 教程

Matplotlib 教程
Web2py 教程

Web2py 教程
BeautifulSoup 教程

BeautifulSoup 教程

Java教程

Java 教程

Java 教程

Web教程

HTML 教程

HTML 教程
CSS 教程

CSS 教程
CSS3 教程

CSS3 教程
jQuery 教程

jQuery 教程
Ajax 教程

Ajax 教程
AngularJS 教程

AngularJS 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程
Laravel 教程

Laravel 教程
Next.js 教程

Next.js 教程
PhantomJS 教程

PhantomJS 教程
Three.js 教程

Three.js 教程
Underscore.JS 教程

Underscore.JS 教程
WebGL 教程

WebGL 教程
WebRTC 教程

WebRTC 教程
VueJS 教程

VueJS 教程

数据库教程

SQL 教程

SQL 教程
MySQL 教程

MySQL 教程
MongoDB 教程

MongoDB 教程
PostgreSQL 教程

PostgreSQL 教程
SQLite 教程

SQLite 教程
Redis 教程

Redis 教程
MariaDB 教程

MariaDB 教程

图形图像教程

Vulkan 教程

Vulkan 教程
OpenCV 教程

OpenCV 教程

大数据教程

R语言 教程

R语言 教程

开发工具教程

Git 教程

Git 教程
VSCode 教程

VSCode 教程
Docker 教程

Docker 教程
Gerrit 教程

Gerrit 教程
Excel 教程

Excel 教程

计算机教程

Go语言 教程

Go语言 教程
C++ 教程

C++ 教程

C++ 示例

登录

找回密码？

注册