文章
时间轴
标签
音乐室
友人帐
一刻时光
清单
留言板
相册
算法海洋
关于
Slcpの童话镇 🏰
写文章
面试题 02.07. 链表相交
简单
数据结构与算法
原题链接
发布日期:
2023年02月26日
文章字数:
5.1k
阅读次数:
484
阅读时长:
0小时0分0秒
![image-20230316105605359](https://img.slcp.top/image-20230316105605359.png) ## 解题思路 - 分别遍历列表,计算列表长度 - 对齐链表长度 - 逐个比较节点内存地址 - 如果内存地址相同即为相交点 - 走到尾部还没有内存地址相同的接口则不想交 > 复杂度分析 时间复杂度:`O(n)`,其中` n `是是链表` headA `和` headB `的长度。 空间复杂度:`O(n)`。 ## 代码 ~~~java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null || headB == null) { return null; } int length1 = 0; int length2 = 0; ListNode p1 = headA; ListNode p2 = headB; while(true) { length1++; if(p1.next == null) { break; } p1 = p1.next; } while(true) { length2++; if(p2.next == null) { break; } p2 = p2.next; } p1 = headA; p2 = headB; if(length1 > length2) { for(int i = 0; i < length1 - length2; i++) { p1 = p1.next; } } if(length2 > length1) { for(int i = 0; i < length2 - length1; i++) { p2 = p2.next; } } while(true) { if(p1 == p2) { return p1; } else { p1 = p1.next; p2 = p2.next; } if(p1 == null || p2 == null) { return null; } } } } ~~~
您阅读这篇文章共耗时:
0小时16分34秒
文章链接:
https://www.slcp.top/article/read/1636199760625205250
版权声明:
本博客所有文章除特別声明外,均采用
CC BY 4.0
许可协议。转载请注明来源
Slcp
!
转载文章以及部分引用均为自己整理记录学习而用,若有侵权,请联系删除。
数据结构与算法
评论
Valine
Gitalk
目录
搜索
首页
前进
后退
刷新
申请友链
在线联系