160.Intersection of Two Linked Lists

Solution 1: HashSet

O(m+n) time

O(m) or O(n) space

/**
 * 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<>();
        ListNode l1 = headA;
        ListNode l2 = headB;
        while(l1 != null){
            set.add(l1);
            l1 = l1.next;
        }
        while(l2 != null){
            if(set.contains(l2)){
                return l2;
            }
            l2 = l2.next;
        }
        return null;
    }
}

Solution 2: Two Pointers

/**
 * 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) {
        ListNode l1 = headA;
        ListNode l2 = headB;
        int len1 = 0;
        int len2 = 0;
        while(l1 != null){
            l1 = l1.next;
            len1 ++;
        }
        while(l2 != null){
            l2 = l2.next;
            len2 ++;
        }
        if(len2 > len1){
            l1 = headB;
            l2 = headA;
        }
        else{
            l1 = headA;
            l2 = headB;
        }
        int diff = Math.abs(len2 - len1);
        for(int i = 0; i < diff; i++){
            l1 = l1.next;
        }
        while(l1 != null){
            if(l1 == l2){
                return l1;
            }
            else{
                l1 = l1.next;
                l2 = l2.next;
            }
        }
        return null;

    }
}

/**
 * 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) {
        if(headA == null && headB == null){
            return null;
        }
        ListNode l1 = headA;
        ListNode l2 = headB;
        while(l1 != l2){
            if(l1 == null){
                l1 = headB;
            }
            else{
                l1 = l1.next;
            }

            if(l2 == null){
                l2 = headA;
            }
            else{
                l2 = l2.next;
            }
        }
        return l1;
    }
}