LeetCode 160: Intersection of Two Linked Lists

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

For example, the following two linked lists:

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

begin to intersect at node c1.

Notes:

• 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.
• Your code should preferably run in O(n) time and use only O(1) memory.

/**
 * 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) {
        // Suppose the lengths are la, lb and lc
        // Maintain two pointers pA and pB initialized at the head of A and B, respectively.
        // Then let them both traverse through the lists, one node at a time.
        // When pA reaches the end of a list, then redirect it to the head of B;
        // Similarly, when pB reaches the end of a list, redirect it the head of A.
        // So pA runs la + lc + lb; pB runs lb + lc + la when they meet at intersection.
        if (headA==null || headB==null)
            return null;
            
        ListNode pA = headA, pB = headB;
        
        // If pA runs la+lc+lb+lc, it still can't qualify pA==pB, then it proves that there isn't intersection.
        int pass = 0;
        
        while (pA != pB)
        {
            pA = pA.next;
            pB = pB.next;
            
            if (pA == null)
            {
                pA = headB;
                pass++;
                
                if (pass == 2)
                    return null;
            }
                
            if (pB == null)
                pB = headA;
        }
        
        return pA;
    }
}