JZ36 两个链表的第一个公共结点

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了JZ36 两个链表的第一个公共结点，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含900字，纯文字阅读大概需要2分钟。

内容图文

两个链表的第一个公共结点

题目：输入两个链表，找出它们的第一个公共结点。

思路：右对齐两个链表，如果两个链表有公共节点，则它们的形状必然是一个Y字形。

长链表先走，实现右对齐，先假设这两个链表的长度相等，则我们可以同步遍历这两个链表，找到公共节点。现在有两个链表，我们可以先分别求齐长度得其差n，然后遍历长的那个链表n个节点，然后同步遍历这两个链表即可。hashmap存储遍历第一条链的节点，遍历另一条，寻找已经出现的key。

 

func abs(x int) int {
    if x  < 0 {
        return -x
    }
    return x
}
func FindFirstCommonNode(pHead1, pHead2  *ListNode) *ListNode {
    if pHead1 == nil || pHead2 == nil {
        return nil
    }
    
    p1, p2 := pHead1, pHead2
    len1, len2 := 0, 0
    for p1 != nil {
        len1++
        p1 = p1.Next
    }
    for p2 != nil {
        len2++
        p2 = p2.Next
    }
    p1 = pHead1
    p2 = pHead2
    if len1 < len2 {
         p1 = pHead2
         p2 = pHead1
    }
    for i := 0;i < abs(len1 - len2);i++ {
        p1 = p1.Next
    }
    for p1 != nil && p2 != nil {
        if p1.Val == p2.Val {
            return p1
        } else {
            p1 = p1.Next
            p2 = p2.Next
        }
    }
    return nil
}

 

　

内容总结

以上是互联网集市为您收集整理的JZ36 两个链表的第一个公共结点全部内容，希望文章能够帮你解决JZ36 两个链表的第一个公共结点所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---