没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
# 【Java】 剑指offer(52) 两个链表的第一个公共结点
> 作者:gdutxiaoxu
微信公众号:徐公码字(stormjun94)
来源:https://github.com/gdutxiaoxu/Android_interview 本文参考自《剑指offer》一书,代码采用Java语言。 **更多《剑指Offer》Java实现合集:https://github.com/gdutxiaoxu/Android_interview ****** ## 题目 输入两个链表,找出它们的第一个公共结点。 ## 思路 蛮力法:遍历第一个链表的结点,每到一个结点,就在第二个链表上遍历每个结点,判断是否相等。时间复杂度为O(m*n),效率低; 使用栈:由于公共结点出现在尾部,所以用两个栈分别放入两个链表中的结点,从尾结点开始出栈比较。时间复杂度O(m+n),空间复杂度O(m+n)。 利用长度关系:计算两个链表的长度之差,长链表先走相差的步数,之后长短链表同时遍历,找到的第一个相同的结点就是第一个公共结点。 利用两个指针:一个指针顺序遍历list1和list2,另一个指针顺序遍历list2和list1,(这样两指针能够保证最终同时走到尾结点),两个指针�
微信公众号:徐公码字(stormjun94)
来源:https://github.com/gdutxiaoxu/Android_interview 本文参考自《剑指offer》一书,代码采用Java语言。 **更多《剑指Offer》Java实现合集:https://github.com/gdutxiaoxu/Android_interview ****** ## 题目 输入两个链表,找出它们的第一个公共结点。 ## 思路 蛮力法:遍历第一个链表的结点,每到一个结点,就在第二个链表上遍历每个结点,判断是否相等。时间复杂度为O(m*n),效率低; 使用栈:由于公共结点出现在尾部,所以用两个栈分别放入两个链表中的结点,从尾结点开始出栈比较。时间复杂度O(m+n),空间复杂度O(m+n)。 利用长度关系:计算两个链表的长度之差,长链表先走相差的步数,之后长短链表同时遍历,找到的第一个相同的结点就是第一个公共结点。 利用两个指针:一个指针顺序遍历list1和list2,另一个指针顺序遍历list2和list1,(这样两指针能够保证最终同时走到尾结点),两个指针�
点击阅读更多
资源评论
半清斋
- 粉丝: 55
- 资源: 322
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功