Write a program to find the node at which the intersection of two singly linked lists begins.

IntersectionNode.java

package com.interviewbytes.linkedlists;

public class IntersectionNode {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        int countA = 0;
        int countB = 0;

        ListNode current = headA;
        while (current != null) {
            current = current.next;
            countA++;
        }

        current = headB;
        while (current != null) {
            current = current.next;
            countB++;
        }

        ListNode small;
        ListNode large;
        int diff;
        if (countA > countB) {
            large = headA;
            small = headB;
            diff = countA - countB;
        } else {
            large = headB;
            small = headA;
            diff = countB - countA;
        }

        while (diff > 0) {
            large = large.next;
            diff--;
        }

        while (large != null /* && small!=null*/) {
            if (large == small) return large;
            large = large.next;
            small = small.next;
        }

        return null;
    }
}

ListNode.java

package com.interviewbytes.linkedlists;

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}