写点什么

判断链表相交

用户头像
GalaxyCreater
关注
发布于: 2020 年 07 月 28 日

判断链表是否相交

// 判断链表是否都相交
func CheckListCross(l1 *List, l2 *List) {
p1 := l1.Front()
p2 := l2.Front()
for p1.Next() != nil {
p1 = p1.Next()
}
for p2.Next() != nil {
p2 = p2.Next()
}
if p1 == p2 && p1 != nil {
fmt.Println("l1 l2 相交")
} else {
fmt.Println("l1 l2 不相交")
}
}

时间复杂度:线性遍历,o(n)= l1长度 + l2长度 = O(n)

空间复杂度: 由于不需要额外创建数组、链接,空间复杂度为1



找出两个链表相交的节点

// 找出两个链表相交于哪一点
func GetListCrossPosition(l1 *List, l2 *List) {
p1 := l1.Front()
p2 := l2.Front()
// 计算两个链表数量
len1 := 0
len2 := 0
for p1.Next() != nil {
p1 = p1.Next()
len1++
}
for p2.Next() != nil {
p2 = p2.Next()
len2++
}
// 确定长短关系
var p *Element = nil
var shortestPtr *Element = nil
step := 0
if len1 > len2 {
step = len1 - len2
p = l1.Front()
shortestPtr = l2.Front()
} else {
step = len2 - len1
p = l2.Front()
shortestPtr = l1.Front()
}
// 最长的链表节点往后移动step步
for i := 0; i < step; i++ {
p = p.Next()
}
// 长短链表节点同时往后遍历
var crossNode *Element = nil
for {
// 找到相交的点
if shortestPtr == p {
crossNode = shortestPtr
break
}
p = p.Next()
shortestPtr = shortestPtr.Next()
// 结束
if p == nil || shortestPtr == nil {
break
}
}
if crossNode != nil {
fmt.Println("l1 l2 相交于", crossNode.Value)
} else {
fmt.Println("l1 l2 不相交")
}
}

时间复杂度:线性遍历, O(n)

空间复杂度: 由于不需要额外创建数组、链接,空间复杂度为1



测试结果:



发布于: 2020 年 07 月 28 日阅读数: 47
用户头像

GalaxyCreater

关注

还未添加个人签名 2019.04.21 加入

还未添加个人简介

评论

发布
暂无评论
判断链表相交