Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
图一：举例
begin to intersect at node c1.
Notes:
- If the two linked lists have no intersection at all, return null.
- The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.
算法分析
方法一：
将链表A加入到set中，检测链表B中的每一个节点是否在set中。
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) {
Set<ListNode> aListNode = new HashSet<>();
while (headA != null) {
aListNode.add(headA);
headA = headA.next;
}
while (headB != null) {
if (aListNode.contains(headB)) return headB;
else headB = headB.next;
}
return null;
}
}
