架构师训练营 8 作业

/**
  *  记忆法，同时遍历，并记录。时间复杂度为m n中最大的那个。但是因为引入了set，导致复杂度变高。并不是期待的O(m)
  */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> nodeSet = new HashSet<>();
        int index = 0;
        while (headA != null || headB!=null) {
            if (headA != null) {
                if (nodeSet.contains(headA)) {
                    return headA;
                }
                nodeSet.add(headA);
                headA = headA.next;
            }
            if (headB == null) {
                continue;
            }
            if (nodeSet.contains(headB)) {
                return headB;
            }
            nodeSet.add(headB);
            headB = headB.next;
        }
        return null;
    }
}

/**
*双指针法，每个指针都跑公共长度  +  双方非公共的长度 ，最终会在距离相等时相遇。时间复杂度为O(m + n - 公共长度)
*/
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;
}