Go语言判断两个链表是否相交的三种方法

链表相交的核心原理

在计算机科学面试与数据结构学习中，判断两个单链表是否相交是一个经典题目。其关键在于理解：如果两个链表相交，它们在最后一个公共节点之后必定完全重合。因此，问题可以转化为寻找两个链表节点序列中的第一个共同引用对象。

针对这一问题，我们通常有三种主要的解决思路：基于额外存储空间的哈希表法、改变原结构以利用环检测法的变通手段，以及最高效的原地双指针法。

准备工作：Go语言链表基础结构

在具体编写算法前，我们需要明确链表的定义以及辅助函数，以便测试不同的相交场景。以下代码定义了标准节点结构，并提供了生成链表和合并（模拟相交）的工具函数。

第1步：定义节点与核心判断逻辑

目的：构建链表模型，并使用最直观的哈希集合来判断是否存在重复引用的节点。

操作说明：创建一个 Node 结构体，包含值和下一个节点的指针。算法通过遍历第一个链表将所有节点存入 map，再遍历第二个链表检查是否有节点已存在于 map 中。

// Node 定义单链表节点
type Node struct {
	val  int
	next *Node
}

// IsIntersectV1 使用 Map 判断是否相交
func IsIntersectV1(list1, list2 *Node) bool {
	if list1 == nil || list2 == nil {
		return false
	}

	// 存储 list1 的所有节点
	visited := make(map[*Node]struct{})
	p := list1
	for p != nil {
		visited[p] = struct{}{}
		p = p.next
	}

	// 检查 list2 中是否有节点在 visited 中
	p = list2
	for p != nil {
		if _, ok := visited[p]; ok {
			return true
		}
		p = p.next
	}

	return false
}

第2步：构建测试用的数据连接工具

目的：方便生成线性链表并手动构造“Y”字形相交结构，用于验证算法准确性。

操作说明：New 函数按数组逆序生成链表；Connect 函数将两个链表串联，常用于模拟两个独立链表最终汇于同一个尾部节点的场景。

// New 根据数组逆序创建新链表
func New(data []int) *Node {
	if len(data) == 0 {
		return nil
	}
	nodes := make([]*Node, len(data))
	for i := 0; i < len(data); i++ {
		nodes[i] = &Node{
			val: data[i],
		}
		if i > 0 {
			nodes[i].next = nodes[i-1]
		}
	}
	return nodes[len(data)-1]
}

// Connect 将 node2 追加到 node1 末尾
func Connect(node1, node2 *Node) *Node {
	if node1 == nil {
		return node2
	}
	if node2 == nil {
		return node1
	}

	p := node1
	for p.next != nil {
		p = p.next
	}
	p.next = node2
	return node1
}

第3步：执行交叉测试

目的：验证上述工具函数的正确性，确保生成的链表结构符合预期。

func main() {
	data1 := []int{1, 2, 3, 4, 5}
	data2 := []int{6, 7, 8, 9, 10}
	data3 := []int{11, 12, 13, 14, 15}

	node1 := New(data1)
	node2 := New(data2)
	node3 := New(data3)

	// 构建相交结构: node2和node3都在末尾接入node1
	node2 = Connect(node2, node1) 
	node3 = Connect(node3, node1) 

	// 此时 node2 和 node3 应共享 node1 的尾部节点
	result := IsIntersectV1(node2, node3)
	fmt.Println("Map方法结果:", result) // 输出: true
}

进阶方案：将链表转化为环检测

除了使用额外的内存空间，还有一种巧妙的方法是借助「环检测」的逻辑。虽然这种方法在实际工程中因修改了原链表结构而不推荐使用，但它展示了算法思维的灵活性。

第1步：破坏性与修复性操作

目的：通过将链表1的尾部指向头部，人为制造一个环，从而判断链表2是否能进入这个环。

风险提醒：此方法会永久改变 `list1` 的拓扑结构，若后续仍需使用该链表可能导致死循环。实际操作后务必恢复原状（将原尾节点的 next 置为 nil）。

// IsIntersectV2 首尾相接法（不推荐生产使用，仅供原理演示）
func IsIntersectV2(list1, list2 *Node) bool {
	if list1 == nil || list2 == nil {
		return false
	}

	// 找到 list1 的尾节点
	p := list1
	for p.next != nil {
		p = p.next
	}
	// 临时将尾节点指向头，形成环
	originalTailNext := p.next // 通常为 nil
	p.next = list1

	defer func() { p.next = originalTailNext }() // 保证执行完恢复现场

	// 遍历 list2，看是否会遇到 list1 的头节点
	p = list2
	for p != nil {
		if p == list1 {
			return true
		}
		p = p.next
	}

	return false
}

最优解：双指针与原地断环法

这是面试中最受推崇的方法。它结合了哈希表的无额外空间优势和快慢指针的定位能力，能够在 O(N) 时间和 O(1) 空间内解决问题。

第1步：双指针同步遍历

入口：初始化两个指针 p1, p2 分别指向 list1 和 list2 的头节点。

动作：同时向后移动。当某个指针到达链表末尾时，将其重新指向另一个链表的头节点。如果两链表相交，它们将在某一时刻相遇；如果不相交，两者都会变成 nil。

// IsIntersectV3 双指针法（推荐）
func IsIntersectV3(list1, list2 *Node) bool {
	if list1 == nil || list2 == nil {
		return false
	}

	p1 := list1
	p2 := list2

	// 注意：这里需要循环直到 p1 == p2，因为可能存在长度差导致的延迟
	// 当 p1 走完 list1 切换到 list2，p2 走完 list2 切换到 list1
	// 第二次经过相交点时必相遇，或者双双变为 nil
	for p1 != p2 {
		if p1 == nil {
			p1 = list2
		} else {
			p1 = p1.next
		}

		if p2 == nil {
			p2 = list1
		} else {
			p2 = p2.next
		}
	}

	return p1 != nil
}

总结

在 Go 语言中处理链表相交问题时，map 方法简单直观但占用 O(N) 空间；首尾相接法体现了算法创意但具有副作用；而**双指针法**则是平衡效率与资源消耗的最佳实践。建议在实际开发中优先掌握双指针的实现逻辑，并注意链表空指针的处理细节。

以上就是Golang判断两个链表是否相交的详细方法内容，更多关于Go算法题的资料请关注本站其它相关文章！