Leetcode-Intersection of Two Linked Lists LCCI

Intersection of Two Linked Lists LCCI

leetcode: https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

Description:

Given two (singly) linked lists, determine if the two lists intersect. Return the inter­ secting node. Note that the intersection is defined based on reference, not value. That is, if the kth node of the first linked list is the exact same node (by reference) as the jth node of the second linked list, then they are intersecting.

Idea:

**solution **

Step1: create the set to record unique elements of one list

Step2: create index to traverse two list, in the first list, add all elements to set. in the loop of second list, check the node of list exists in the set or not, if exists return the node.

Step3: if no intersection, return null.

Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //create index to traverse two list
        ListNode a = headA;
        ListNode b = headB;
        //create the set to record node
        Set<ListNode> record = new HashSet<>();
        //add node to set
        while(a != null){
            record.add(a);
            a = a.next;
        }
        //if the node in b exists in the set, it means there exists intersect
        while(b != null){
            if(record.contains(b)){
                return b;
            }
            b = b.next;
        }
        return null;
    }
}