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.

Solution 1: calculate the length of A and B first. Move the pointer to be same length from end. keep moving the two pointer until they meet up. Return the node.

 public class Solution {  
   public ListNode getIntersectionNode(ListNode headA, ListNode headB) {  
     int c1=0, c2=0;  
     ListNode p=headA;  
     while (p!=null) {  
       p=p.next;  
       c1++;  
     }  
     p=headB;  
     while (p!=null) {  
       p=p.next;  
       c2++;  
     }  
     ListNode p1=headA, p2=headB;  
     while (c1>c2) {  
       p1=p1.next;  
       c1--;  
     }  
     while (c2>c1) {  
       p2=p2.next;  
       c2--;  
     }  
     while (p1!=null && p1!=p2) {  
       p1=p1.next;  
       p2=p2.next;  
     }  
     return p1;  
   }  
 }