判断两个链表是否相等，指的是两个链表的节点数量、每个节点存储的数据值、节点的排列顺序都完全一致，只要有一项不满足就视为两个链表不相等。这个判断逻辑在链表去重、链表对比等场景中非常实用。
基础判断思路
最直观的判断方式是同时遍历两个链表，逐个对比每个节点的数据，直到两个链表都遍历完成。这个思路的核心是先判断两个链表的长度是否一致，如果长度不同直接返回不相等，避免后续无效的遍历操作。
步骤拆解
- 首先判断两个链表头节点是否都为空，如果都为空则直接返回相等
- 如果只有一个头节点为空，另一个不为空，直接返回不相等
- 同时移动两个链表的指针，每次移动后对比当前节点的数据值
- 如果任意一次对比数据值不同，直接返回不相等
- 当两个指针都移动到链表末尾时，说明所有节点都匹配，返回相等
代码实现示例
以下是使用Python语言实现的判断逻辑，假设链表节点的定义如下：
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
判断两个链表是否相等的完整函数实现：
def is_list_equal(head1, head2):
# 两个链表都为空的情况
if head1 is None and head2 is None:
return True
# 只有一个链表为空的情况
if head1 is None or head2 is None:
return False
# 同时遍历两个链表
p1 = head1
p2 = head2
while p1 is not None and p2 is not None:
# 对比当前节点的数据值
if p1.val != p2.val:
return False
p1 = p1.next
p2 = p2.next
# 遍历结束后判断是否都到达末尾
return p1 is None and p2 is None
复杂度分析
这种遍历方式的效率非常高，我们可以从时间复杂度和空间复杂度两个方面分析：
| 复杂度类型 | 数值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | n为两个链表中较短的那个的长度，最多遍历完较长的链表即可完成判断 |
| 空间复杂度 | O(1) | 只使用了固定的几个指针变量，没有额外的空间开销 |
常见错误避坑
在实际实现过程中，开发者很容易出现以下错误：
- 忘记判断两个链表长度是否一致，只对比到其中一个链表结束就认为相等，这会导致短链表是长链表的前半部分时被误判为相等
- 对比节点时直接对比节点对象本身，而不是对比节点的
val属性，不同节点对象即使数据相同也会被判为不相等 - 处理空链表的情况时逻辑遗漏，比如一个链表为空另一个不为空时返回相等
扩展场景说明
如果链表是带有环的链表，上述判断逻辑仍然适用吗？如果判断的相等要求包含环的结构也一致，那么上述逻辑只能判断到环入口之前的节点，需要额外判断环的入口位置是否一致。如果只需要判断环之前的部分节点相等，原有的逻辑可以正常使用。
注意：如果链表节点存储的是复杂对象，需要对比对象的内容是否相等，而不是直接对比对象的引用，这时候需要根据实际的数据结构重写对比逻辑。