相交链表

160.相交链表

由题目要求可以知道，题目数据保证了不会出现环形

注意，函数返回结果后，链表必须 保持其原始结构 。

方法一：哈希集合

利用哈希表的特性，不能放重复元素

判断两个链表是否相交，可以将结点存储在哈希集合里，因为哈希集合里的元素是不允许重复的

首先遍历链表 headA，将链表 headA 中的元素加入哈希集合中，然后遍历 headB，对于遍历的结点，判断该节点是否已经添加过

• 如果当前节点不在哈希集合中，继续下一个节点
• 如果在集合中，该节点就是相交的节点，返回即可
• 如果 headB 中的所有节点都不在，则两个链表不相交，返回 null

public class Solution {
	public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    	if (headA == null || headB == null) {
            return null;
        }
        Set<ListNode> visited = new HashSet<>();
        ListNode h = headA;
        while (h != null) {
        	visited.add(h);
            h = h.next;
        }
        h = headB;
        while (h != null) {
            // 这个也可以满足条件
        	//if (visited.contains()) {
            //	return h;
            //}
            
        	if (!visited.add(h)) {
                return h;
            }
            h = h.next;
        }
        return null;
    }
}

方法二：双指针

使用双指针可以将空间复杂度降到 O(1)

只有当 headA 和 headB 都不为空时，两个链表才会相交，所以先判断链表是否为空

当链表 headA 和 headB 都不为空时，创建两个指针pA，pB，分别从 headA 和 headB开始，遍历链表，操作如下：

• 每步都需要同时更新指针 pA 和 pB
• 如果 pA 不为空，则移向下一个节点；如果为空，则将指针 pA 移到链表 headB 的头结点
• 如果 pB 不为空，则移向下一个节点；如果为空，则将指针 pB 移到链表 headA 的头结点
• 当指针 pA 和 pB 指向同一个节点或者都为空时，返回他们指向的结点或null

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;
    }
}