Cross linked list

Given two single linked lists, headA and headB, you are asked to find and return the starting node where the two lists intersect. If two lists do not intersect, null is returned.

For details, see the LeetCode official website.

Source: LeetCode link: leetcode-cn.com/problems/in… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution 1: HashSet

Use Java HashSet to deduplicate, iterate over the two linked lists headA and headB, put each node in HashSet notRepeatNodes, if it can be put in, it means it is not intersected, and continue to iterate over the next node; If you can’t put it in, since headA and headB don’t have a loop, this node is the intersection, return the current node. If the two lists do not intersect each other, return null.

import java.util.HashSet;
import java.util.Set;

public class LeetCode_160 {
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        Set<ListNode> notRepeatNodes = new HashSet<>();
        ListNode nextA = headA;
        ListNode nextB = headB;
        while(nextA ! =null|| nextB ! =null) {
            if(nextA ! =null) {
                if(! notRepeatNodes.add(nextA)) {return nextA;
                } else{ nextA = nextA.next; }}if(nextB ! =null) {
                if(! notRepeatNodes.add(nextB)) {return nextB;
                } else{ nextB = nextB.next; }}}return null;
    }

    public static void main(String[] args) {
        ListNode headA = new ListNode(1);
        headA.next = new ListNode(9);
        headA.next.next = new ListNode(1);

        ListNode headB = new ListNode(3);

        ListNode commonNode = new ListNode(2);

        headA.next.next.next = commonNode;
        headB.next = commonNode;
        commonNode.next = new ListNode(4);

        ListNode result = getIntersectionNode(headA, headB);
        if (result == null) {
            System.out.println("Disjunction");
        } else{ System.out.println(result.val); }}}Copy the code

With a tolerant heart to live, no matter how crowded the world will become infinitely broad, no matter how ordinary life will become full of sunshine.