C++程序 检查两个链表是否相同

当两个链表的数据相同且排列方式也相同时，它们是相同的。例如，链表a(1->2->3)和b(1->2->3)是相同的。编写一个函数来检查给定的两个链表是否相同。

方法1(迭代)：

对于要识别两个列表是否相同，我们需要同时遍历两个列表，遍历时需要比较数据。

// 用于检查两个链表是否相同的迭代C++程序
#include
using namespace std;
 
// 链表结构
struct Node
{
    int data;
    struct Node *next;
};
 
/* 如果链表a和b相同，则返回true，否则返回false */
bool areIdentical(struct Node *a,
                 struct Node *b)
{
    while (a != NULL && b != NULL)
    {
        if (a->data != b->data)
            return false;
 
        /* 如果到达这里，则a和b不是NULL，其数据相同in，因此在两个列表中移动到下一个节点 */
        a = a->next;
        b = b->next;
    }
 
    // 如果链表相同，则此时'a'和'b'必须为NULL。
    return (a == NULL && b == NULL);
}
 
/* 测试fun1()和fun2()的实用函数 */
/* 给定一个引用（指向指针）指向列表头和一个整数，将列表的新节点推到列表的前面 */
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;
}
 
// 驱动程序
int main()
{
    /* 构造的链表如下：
           a: 3->2->1
           b: 3->2->1 */
    struct Node *a = NULL;
    struct Node *b = NULL;
    push(&a;, 1);
    push(&a;, 2);
    push(&a;, 3);
    push(&b;, 1);
    push(&b;, 2);
    push(&b;, 3);
 
    if(areIdentical(a, b))
        cout << "相同";
    else
        cout << "不相同";
 
    return 0;
}
// 该代码由Akanksha Rai贡献```  

输出:

相同

时间复杂度 ：O(n)，其中n是a和b中长度较小的列表的长度。

方法2 (递归)：

递归解决方案的代码比迭代代码要更干净。但是，您可能不想在生产代码中使用递归版本，因为它将使用与列表长度成比例的堆栈空间。

// 用于检查两个链表是否相同的C ++递归函数
bool areIdentical(Node *a, Node *b)
{
    // 如果两个列表都为空
    if (a == NULL && b == NULL)
    return true;
 
    // 如果两个列表都不为空，则当前节点的数据必须匹配，对于剩下的节点也必须递归地匹配。
    if (a != NULL && b != NULL)
    return (a->data == b->data) &&
            areIdentical(a->next, b->next);
 
    // 如果到达这里，则其中一个列表为空而另一个不为空
    return false;
}
// 由rathbhupendra贡献此代码```  

时间复杂度： 无论是迭代版本还是递归版本的时间复杂度均为O(n)，其中n是a和b中长度较小的列表的长度。

辅助空间： 因使用递归而导致调用栈的空间复杂度为 O(n)