题目

输入两个链表，找出它们的第一个公共节点。
有两种情况：有相交结点和无相交结点

题解

双指针法

（思路如图，但是图放不上来）
双指针法与哈希法相比，降低了空间复杂度

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode node1 = headA, node2 = headB;while( node1!=node2 ) {if( node1!=null ) node1 = node1.next;else node1 = headB;if( node2!=null ) node2 = node2.next;else node2 = headA;}return node1;}
}

HashSet法

代码

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {HashSet<ListNode> store = new HashSet<>();ListNode node = headA;while( node!=null ) {store.add(node);node = node.next;}while( headB!=null ) {if(store.contains(headB)) return headB;headB = headB.next;}return headB;}
}

HashSet

构造方法HashSet<ListNode> store = new HashSet<>();
add()
contains()
remove()
size()
clear()

HashSet用于储存对象， HashMap用于储存键值对