LeetCode160-相交链表

LeetCode160-相交链表

利用哈希Map实现(O(m+n))

1
2
3
4
5
6
7
8
9
10
11
12
13
HashMap<ListNode,Object> map = new HashMap<>();
//遍历链表
ListNode dummyHeadA = headA;
while (dummyHeadA!=null){
map.put(dummyHeadA,null);
dummyHeadA = dummyHeadA.next;
}
dummyHeadA = headB;
while (dummyHeadA!=null){
if (map.containsKey(dummyHeadA)) return dummyHeadA;
dummyHeadA = dummyHeadA.next;
}
return null;

双指针(O(m+n))

1
2
3
4
5
6
7
8
9
10
11
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;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!