160. Intersection of Two Linked List.md

Solution1

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        int lenA = getSize(headA), lenB = getSize(headB);
        while (lenA > lenB) {
            headA = headA.next;
            lenA--;
        }
        while (lenB > lenA) {
            headB = headB.next;
            lenB--;
        }
        while (headA != null && headB != null && headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        if (headA != null) {
            return headA;
        }
        return null;
    }
    private int getSize(ListNode head) {
        int size = 1;
        ListNode node = head;
        while (node.next != null) {
            size++;
            node = node.next;
        }
        return size;
    }
}

note

• time O(n) space O(1)
• The idea is to find the length of two linked lists, move pointers on the longer lists first to achieve equal length of the rest of the list. Then, move two pointers on two lists together and see if they have the same node at some point. If so, this ois the intersection node. Otherwise, return null.