本网站(662p.com)打包出售,且带程序代码数据,662p.com域名,程序内核采用TP框架开发,需要联系扣扣:2360248666 /wx:lianweikj
精品域名一口价出售:1y1m.com(350元) ,6b7b.com(400元) , 5k5j.com(380元) , yayj.com(1800元), jiongzhun.com(1000元) , niuzen.com(2800元) , zennei.com(5000元)
需要联系扣扣:2360248666 /wx:lianweikj
Golang判断两个链表是否相交的方法详解
五星人 · 132浏览 · 发布于2023-03-14 +关注

这篇文章主要为大家详细介绍了如何通过Golang判断两个链表是否相交,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下

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

面试中可能会问到的算法题,今天总结一下

方法一:map

步骤:

  • 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
}


相关推荐

PHP实现部分字符隐藏

沙雕mars · 1312浏览 · 2019-04-28 09:47:56
Java中ArrayList和LinkedList区别

kenrry1992 · 896浏览 · 2019-05-08 21:14:54
Tomcat 下载及安装配置

manongba · 957浏览 · 2019-05-13 21:03:56
JAVA变量介绍

manongba · 953浏览 · 2019-05-13 21:05:52
什么是SpringBoot

iamitnan · 1076浏览 · 2019-05-14 22:20:36
加载中

0评论

评论
分类专栏
小鸟云服务器
扫码进入手机网页