Simple Java solution, time - O(n), space - O(1). Just get the difference in sizes and iterate.


  • 2
    P
    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) return null;
            ListNode a,b;
            a = headA;
            b = headB;
            int sizeA, sizeB;
            sizeA = sizeB = 0;
            //get the size of the lists
            for(;a != null; a = a.next)
                sizeA++;
            for(;b != null; b = b.next)
                sizeB++;
            a = headA;            
            b = headB;
            int sizeDiff = sizeA > sizeB ? sizeA - sizeB: sizeB - sizeA;//get the difference in sizes
            int bigger = sizeA > sizeB ? sizeA : sizeB;//get the size of the bigger one
            //advance a or b (depending on whose size is bigger so that both are at the same distance
            //from the end
            if (sizeA > sizeB){
                for(int i = 0; i < sizeDiff; i++)
                    a = a.next;
            }
            else if (sizeB > sizeA){
                for(int i = 0; i < sizeDiff; i++)
                    b = b.next;
            }
            //now a and b are at same distance from the end
            for(int i = 0; i < bigger - sizeDiff; i++){
                if (a == b)//compare the memore address
                    return a;
                a = a.next;
                b = b.next;
            }
            //no intersection found
            return null;        
        }
    }

  • 0
    G
    This post is deleted!

  • 0
    P

    Which line of code do you think will throw an exception?


  • 0
    G

    My comment was meant for a different post.... You code is perfect... I am sorry!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.