您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
这篇文章主要介绍“Golang如何判断两个链表是否相交”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“Golang如何判断两个链表是否相交”文章能帮助大家解决问题。
步骤:
1.遍历list1,以节点为key放入map中
2.遍历list2,判断每个节点是否在map中,如果在则相交,且顶一个存在的节点是交点
// 定义链表节点 type Node struct { val int next *Node } // 判断两个链表是否相交 func IsIntersect(list1, list2 *Node) bool { if list1 == nil || list2 == nil { return false } m := make(map[*Node]struct{}) p := list1 for p != nil { m[p] = struct{}{} p = p.next } p = list2 for 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 := node1 for p.next != nil { p = p.next } p.next = node2 return 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,1 node3 = Connect(node3, node1) // 15,14,13,12,11,5,4,3,2,1 result := 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 := list1 for p.next != nil { p = p.next } p.next = list1 // 遍历链表2,如果能到达链表1的头则说明相交 p = list2 for p != nil { if p == list1 { return true } p = p.next } return false }
关于“Golang如何判断两个链表是否相交”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识,可以关注亿速云行业资讯频道,小编每天都会为大家更新不同的知识点。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。