Golang如何判斷兩個(gè)鏈表是否相交

這篇文章主要介紹“Golang如何判斷兩個(gè)鏈表是否相交”的相關(guān)知識(shí)，小編通過(guò)實(shí)際案例向大家展示操作過(guò)程，操作方法簡(jiǎn)單快捷，實(shí)用性強(qiáng)，希望這篇“Golang如何判斷兩個(gè)鏈表是否相交”文章能幫助大家解決問(wèn)題。

算法題：判斷2個(gè)鏈表相交

方法一：map

步驟：

• 1.遍歷list1,以節(jié)點(diǎn)為key放入map中

• 2.遍歷list2,判斷每個(gè)節(jié)點(diǎn)是否在map中，如果在則相交，且頂一個(gè)存在的節(jié)點(diǎn)是交點(diǎn)

// 定義鏈表節(jié)點(diǎn)
type Node struct {
	val  int
	next *Node
}

// 判斷兩個(gè)鏈表是否相交
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
}

// 根據(jù)數(shù)組生成鏈表
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]
}

// 合并兩個(gè)鏈表
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
}

測(cè)試

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，看是否能達(dá)到鏈表1的頭，如果能則說(shuō)明相交

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，如果能到達(dá)鏈表1的頭則說(shuō)明相交
	p = list2
	for p != nil {
		if p == list1 {
			return true
		}

		p = p.next
	}

	return false
}

關(guān)于“Golang如何判斷兩個(gè)鏈表是否相交”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會(huì)為大家更新不同的知識(shí)點(diǎn)。