160 Intersection of Two Linked Lists

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

两个指针遍历链表，A 链表的指针遍历完后从 B 链表的开头继续遍历，B 链表的指针遍历完后从 A 链表的开头继续遍历。如果有交点，两个指针都从头遍历一次后会在交点相遇。如果没有，两个指针第二次会同时到队尾，同时为 null 。时间复杂度 O(n) ，空间复杂度 O(1)

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1=headA, p2=headB;
        while(p1 != p2){
            p1 = p1 == null ? headB : p1.next;
            p2 = p2 == null ? headA : p2.next;
        }
        return p1;
    }
}

也可以用 hash 表，时间复杂度 O(n) ，空间复杂度 O(n)

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