Simulation

Solution 1 HashSet

By adding all the node in List 1 in to a HashSet, and traverse the List 2 to find it first node that equals.

Solution 2 List Traverse

Find the length difference of two list. Let the longer list run the difference first.

Solution 3 List Traverse Optimized

1. Scan both lists
2. For each list once it reaches the end, continue scanning the other list
3. Once the two runner equal to each other, return the position

Implementation

Solution 1

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

Solution 2

Solution 3

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode tempHeadA = headA;
    ListNode tempHeadB = headB;
    while (!(headA == null && headB == null)) {
        if (headA == headB) {
            return headA;
        }
        if (headB == null) {
            headB = tempHeadA;
        } else if (headA == null) {
            headA = tempHeadB;
        } else {
            headA = headA.next;
            headB = headB.next;
        }
    }
    return null;
}

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA==null || headB == null)
            return null;
        ListNode tempA = headA, tempB = headB;
        while(tempA!=tempB){
            tempA = tempA==null ?headB:tempA.next;
            tempB = tempB==null ?headA:tempB.next;
        }
        return tempA;
    }