Intersection of Two Linked Lists

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

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.

Example:

The following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Solution:

• find the length of A and B (lenA, lenB)
• if lenA > lenB, linked list A need to forward lenA - lenB nodes; if lenB > lenA, linked list B need to forward lenB nodes.
• forward both A and B, if we find both A and B are pointing to same node, return it; if we travel all nodes in both A and B, return null.

Code:

public class Solution {
    /**
     * @param headA: the first list
     * @param headB: the second list
     * @return: a ListNode 
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        int lenA = findLength(headA);
        int lenB = findLength(headB);
        ListNode curA = headA;
        ListNode curB = headB;
        if (lenA > lenB) {
            curA = moveK(curA, lenA - lenB);
        } else if (lenA < lenB) {
            curB = moveK(curB, lenB - lenA);
        }
        while (curA != null && curB != null) {
            if (curA == curB) {
                return curA;
            } else {
                curA = curA.next;
                curB = curB.next;
            }
        }
        return null;
    } 

    private int findLength(ListNode root) {
        int len = 0;
        while (root != null) {
            len++;
            root = root.next;
        }
        return len;
    }

    private ListNode moveK(ListNode root, int k) {
        for (int i = 0; i < k; i++) {
            if (root != null) {
                root = root.next;
            }
        }
        return root;
    }
}