Golang如何判断两个链表是否相交

发布时间:2023-03-14 09:40:46 作者:iii
来源:亿速云 阅读:99

这篇文章主要介绍“Golang如何判断两个链表是否相交”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“Golang如何判断两个链表是否相交”文章能帮助大家解决问题。

算法题:判断2个链表相交

方法一: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如何判断两个链表是否相交”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识,可以关注亿速云行业资讯频道,小编每天都会为大家更新不同的知识点。

推荐阅读:
  1. golang如何使用私有的字段
  2. golang如何统一更改字段的命名风格

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

golang

上一篇:怎么用Python程序实现向MySQL存放图片

下一篇:Mysql中如何使用时间查询

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》