[数据结构与算法]160. 相交链表

160. 相交链表

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

用HashSet记录是否相等，如果节点相等说明他们相交。

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

A的长度为m，B的长度为n， A不相交的部分长度为a，B不相交的部分长度为b，相交部分长度为c。

那么 A遍历的是 a + c + b + c;

B遍历的是b + c + a + c;他们会在后一个c的时候相遇，直接返回即可，如果c == 0，则最后会遍历完m + n，返回null，符合题意