写点什么

算法: 链表是否重合查询

发布于: 2020 年 11 月 15 日

思路:

因为两个链表长度可能不同,假如有交合点。

就像操场跑圈,让跑得快的链表跑慢点,让跑得慢的人跑快点,他们总会相遇。

如果一直跑不相遇,就是没有交合点。

算法复杂度:

时间: O(N)

空间: O(1)

public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null){
return null;
}
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}



用户头像

还未添加个人签名 2018.10.01 加入

还未添加个人简介

评论

发布
暂无评论
算法:链表是否重合查询