判断两个单链表相交的3种方法（C语言实现）_如何高效判断两条单链表是否相交

判断 2 个单链表是否相交，是一个老生常谈但又极具思考性的面试题，本节就在读者已经掌握单链表及其基本操作的基础上，就此问题给大家做深入地讲解。

首先，读者要搞清楚“相交”的含义。所谓相交，是指有公共的部分，而 2 个单链表相交，则意味着它们有公共的节点，公共节点的数量可以是 1 个或者多个。

通过前面的学习我们知道，单链表是线性表的一种，如果我们将 2 个单链表看做 2 条线段的话，图 1 模拟了 2 条线段相交的所有可能情况。

图 1 链表相交

注意，结合“单链表中每个节点有且仅有 1 个指针域”的特性，如 1 所示的这 3 种情况中，只有第 2 种情况符合单链表的特性，另外 2 种情况则破坏了此特性。经过以上的分析，本节要验证 2 个单链表是否相交，实际上等同于判断 2 个单链表是否和图 1② 所示的存储结构相同。

判断 2 个单链表（下文分别称它们为链表 1 和链表 2 ）是否相交，常用的方法有如下几种。

哪里不懂问哪里，助力初学者和计算机考研党快速入门数据结构，需要一对一答疑服务的（答疑范围主要是我写的数据结构教程），加 q