160. Intersection of Two Linked Lists Leetcode Java

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.

Solution:
The easiest way is to count the length of List A and B respectively. And we can get the difference of this two lists, Eg. A has length 5, and B has length 6, so we get the difference of 1 and we set the starting position of pointer i at a1 and j at b2, and traversal the two lists till two pointers met at the intersection points.

My solution is similar, I maintained two pointers curA and curB, starting from a1 and b1 respectively, when curA hit the tail of the A, we set curA = B's head, and when curB hit the tail of B we set curB= A's head, by doing this way, when curB=a1, curA=b2, so when they meet, they will meet at the intersection, or if there is no intersection, they won't meet.

  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {  
    if(headA==null || headB==null) return null;  
    ListNode curA=headA;  
    ListNode curB=headB;  
    int count=0;  
    while(count<2 && curA!=curB){  
      curA=curA.next;  
      curB=curB.next;  
      if(curA==null){  
        curA=headB;  
        count++;  
      }  
      if(curB==null) curB=headA;  
    }  
    if(curA==curB) return curA;  
    return null;  
   }