Golang判斷兩個鏈表是否相交的方法詳解
更新時間：2023年03月14日 08:41:30 作者：nil
這篇文章主要為大家詳細介紹了如何通過Golang判斷兩個鏈表是否相交，文中的示例代碼講解詳細，感興趣的小伙伴可以跟隨小編一起學習一下
算法題：判斷2個鏈表相交
面試中可能會問到的算法題，今天總結(jié)一下
方法一：map
步驟：
- 1.遍歷list1,以節(jié)點為key放入map中
- 2.遍歷list2,判斷每個節(jié)點是否在map中，如果在則相交，且頂一個存在的節(jié)點是交點
// 定義鏈表節(jié)點
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
}
// 根據(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]
}
// 合并兩個鏈表
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判斷兩個鏈表是否相交的方法詳解的文章就介紹到這了,更多相關Golang判斷鏈表是否相交內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
最近在做性能優(yōu)化,有個函數(shù)里面的耗時特別長,看里面的操作大多是一些字符串拼接的操作,而字符串拼接在 golang 里面其實有很多種實現(xiàn),下面這篇文章主要給大家介紹了關于Golang語言如何高效拼接字符串的相關資料,需要的朋友可以參考下2023-04-04
本篇文章主要介紹了go語言net包rpc遠程調(diào)用的使用示例，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-11-11
策略是一種行為設計模式,?它將一組行為轉(zhuǎn)換為對象,?并使其在原始上下文對象內(nèi)部能夠相互替換,本文就將通過代碼示例給大家詳細的介紹一下Go的策略模式,需要的朋友可以參考下2023-08-08
這篇文章主要介紹了golang?run時報undefined錯誤的解決方案,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-03-03
Go map底層實現(xiàn)與擴容規(guī)則和特性分類詳細講解
這篇文章主要介紹了Go map底層實現(xiàn)與擴容規(guī)則和特性，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習吧2023-03-03
函數(shù)是編程中不可或缺的組成部分，在本文中，我們將詳細介紹Go語言中函數(shù)的概念和使用方法，包括函數(shù)的定義、參數(shù)和返回值等，需要的可以參考一下2023-06-06
本文將介紹?Go?語言中的?sync.Pool并發(fā)原語，包括sync.Pool的基本使用方法、使用注意事項等的內(nèi)容，對我們了解Go語言有一定的幫助，需要的可以參考一下2023-04-04
這篇文章主要為大家詳細介紹了使用Go語言實現(xiàn)找出兩個大文件中相同的記錄的相關知識,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下2024-10-10
這篇文章主要給大家介紹了關于Golang基礎教程之字符串string的相關資料,需要的朋友可以參考下2022-07-07
這篇文章主要為大家詳細介紹了如何使用Go語言實現(xiàn)自制簡單易用的Web框架,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下2024-01-01