算法: 链表是否重合查询
思路:
因为两个链表长度可能不同,假如有交合点。
就像操场跑圈,让跑得快的链表跑慢点,让跑得慢的人跑快点,他们总会相遇。
如果一直跑不相遇,就是没有交合点。
算法复杂度:
时间: O(N)
空间: O(1)
因为两个链表长度可能不同,假如有交合点。
就像操场跑圈,让跑得快的链表跑慢点,让跑得慢的人跑快点,他们总会相遇。
如果一直跑不相遇,就是没有交合点。
时间: 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 加入
还未添加个人简介
促进软件开发及相关领域知识与创新的传播
评论