L160. Intersection of Two Linked Lists

LinkedList

Problem

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

For example, the following two linked lists:

begin to intersect at node c1.

Solution:

• make sure two pointers reach the intersection node at the same time.

• use two iterations to do that

  • reset the pointer of one linkedlist to the head of another linkedlist after it reaches the tail node

  • move two pointers until they points to the same node

public ListNode intersection(ListNode headA, ListNode headB){
    if(headA == null || headB == null) return null;
    ListNode p1 = headA, p2 = headB;
    while(p1 != p2){
        p1 = p1 != null ? p1.next: headB;
        p2 = p2 != null ? p2.next: headA;
    }
    return p1;   
}