[leetcode] Intersection of Two Linked Lists

problem

code

1st try: with HashSet

if there is a ListNode that both A and B have, the reference address of the ListNode is equal

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

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

Time: O(N)
Space: O(N)

2nd try: two pointer solution

8 is the intersection of two singly linked lists begins.
headA = [4,1,8,4,5]
headB = [5,6,1,8,4,5]

headA => 4, 1, 8, 4, 5, 5, 6, 1, <8>
headB => 5, 6, 1, 8, 4, 5, 4, 1, <8>

!!! size:
headA + headB = headB + headA

cases)
1. the size of A and B are euqal
2. the size of one Linked list is bigger than the other

If there is an intersection, we can find the intersection within A.size + b.size iterations.
If there is no intersection, loop stops and return null

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    let first = headA;
    let second = headB;
    
    while (first != second) {
        first = !first ? headB : first.next;
        second = !second ? headA : second.next;
    }
    
    return first;
};

O(N) time,
O(1) space