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

在C++编程中，经常需要判断两个链表是否相同。两个链表相同指的是它们具有相同的长度，并且对应位置上的元素也相同。本文将介绍如何编写一个C++程序来检查两个链表是否相同。

算法介绍

检查两个链表是否相同的基本算法是遍历这两个链表，逐一比较它们对应位置上的元素。如果它们长度和元素都相同，则这两个链表就是相同的。算法的时间复杂度是O(n)，其中n是链表的长度。

下面是基于这个算法的C++程序示例：

#include <iostream>
using namespace std;

//链表节点结构体定义
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {} //构造函数
};

//检查两个链表是否相同的函数
bool isSameList(ListNode *p, ListNode *q) {
    while(p && q){
        if(p->val != q->val)
            return false;
        p = p->next;
        q = q->next;
    }
    return !p && !q;
}

函数isSameList的参数是两个链表的头节点。函数返回值是一个bool类型的值，表示这两个链表是否相同。

在函数isSameList中，我们使用了while循环遍历这两个链表。当两个链表中至少有一个已经遍历完时，循环结束。在循环遍历的过程中，每次比较这两个链表对应位置上的元素。如果它们不相同，则这两个链表就不相同，并可以立即返回false。否则继续遍历这两个链表，直到两个链表均被遍历完。最后，如果两个链表均已被遍历完，且没有发现不相同的元素，则这两个链表就是相同的。

实例演示

下面是函数isSameList的测试代码：

int main() {
    //建立第一个链表: 1->2->3->NULL
    ListNode *p = new ListNode(1);
    p->next = new ListNode(2);
    p->next->next = new ListNode(3);

    //建立第二个链表: 1->2->3->NULL
    ListNode *q = new ListNode(1);
    q->next = new ListNode(2);
    q->next->next = new ListNode(3);

    //检查两个链表是否相同
    bool result = isSameList(p, q);

    //输出结果
    cout << "The result is: " << (result ? "True" : "False") << endl;
    return 0;
}

上述测试代码创建了两个链表，它们均包含三个元素，且这两个链表的元素都是相同的。程序调用了函数isSameList来判断这两个链表是否相同。在这个例子中，函数isSameList应该返回true。程序最后输出The result is: True，表示这两个链表是相同的。