Solution using HashMap - O(n) time and O(1) space


  • 0
    C
    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if(headA == null || headB == null)
                return null;
                
            HashMap<Integer,ListNode> map = new HashMap<Integer,ListNode>();
            while(headA != null)
            {
                map.put(headA.val,headA.next);
                headA = headA.next;
            }
            
            ListNode ans = null;
            boolean check = false;
            while(headB != null)
            {
                if(map.containsKey(headB.val) && map.get(headB.val) == headB.next)
                {
                    if(!check)
                    {
                        ans = headB;
                        check = true;
                    }
                }
                else
                {
                    check = false;
                }
                headB = headB.next;
            }
            return ans;
        }
    }
    

Log in to reply
 

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