这篇文章主要介绍“Golang如何判断两个链表是否相交”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“Golang如何判断两个链表是否相交”文章能帮助大家解决问题。
算法题:判断2个链表相交
方法一:map
步骤:
遍历list1,以节点为key放入map中
遍历list2,判断每个节点是否在map中,如果在则相交,且顶一个存在的节点是交点
// 定义链表节点type Node struct {val intnext *Node}// 判断两个链表是否相交func IsIntersect(list1, list2 *Node) bool {if list1 == nil || list2 == nil {return false}m := make(map[*Node]struct{})p := list1for p != nil {m[p] = struct{}{}p = p.next}p = list2for p != nil {if _, ok := m[p]; ok {return true}p = p.next}return false}// 根据数组生成链表func New(data []int) *Node {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]}// 合并两个链表func Connect(node1, node2 *Node) *Node {if node1 == nil {return node2}if node2 == nil {return node1}p := node1for p.next != nil {p = p.next}p.next = node2return node1}
测试
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 = Connect(node2, node1) // 10,9,8,7,6,5,4,3,2,1node3 = Connect(node3, node1) // 15,14,13,12,11,5,4,3,2,1result := data0312.IsIntersect(node2, node3)fmt.Println(result) // true}
方法二:首尾相接法
将链表1的尾指向头,然后遍历链表2,看是否能达到链表1的头,如果能则说明相交
func IsIntersect(list1, list2 *Node) bool {if list1 == nil || list2 == nil {return false}// 将链表1的尾指向头p := list1for p.next != nil {p = p.next}p.next = list1// 遍历链表2,如果能到达链表1的头则说明相交p = list2for p != nil {if p == list1 {return true}p = p.next}return false}
关于“Golang如何判断两个链表是否相交”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识,可以关注编程网行业资讯频道,小编每天都会为大家更新不同的知识点。