160. Intersection of Two Linked Lists

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

计算两个链表的长度。将长的链表向下移动两者长度的差，对齐两个链表的长度。
同时向下移动两个链表，如果两个节点的内存地址相同，则返回节点。否则返回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) {
        int sizeA = 0, sizeB = 0;
        ListNode l1 = headA, l2 = headB;
            
        while(l1 != null){
            l1 = l1.next;
            sizeA++;
        }
        while(l2 != null){
            l2 = l2.next;
            sizeB++;
        }
        if(sizeA > sizeB){
            int size = sizeA - sizeB;
            while(size != 0){
                headA = headA.next;
                size--;
            }
        }
        else{
            int size = sizeB - sizeA;
            while(size != 0){
                headB = headB.next;
                size--;
            }
        }
        while(headA != null){
            if(headA == headB) return headA;
                headA = headA.next;
                headB = headB.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) {
        HashSet<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;
    }
}