This is the first day of my participation in the More text Challenge. For details, see more text Challenge

The title

Given two singly linked lists that may or may not have a loop, the head nodes are head1 and head2. Implement a function that, if two lists intersect, returns the first node where they intersect. If they do not intersect, null is returned

Requirement: if the sum of two lists is N, the time complexity is O(N), and the extra space complexity is O(1).

Train of thought

1. First, there are three big situations

1.1 Neither head1 nor head2 has loops

1.2 Both head1 and head2 have loops

1.3 One of head1 and head2 has a ring and the other has no ring

2. We use a function getLoop to determine whether a list has a loop.

If the list has a loop, the fast pointer will meet the slow pointer. If there is no loop, the fast pointer will be null first

  public Node getLoop(Node head) { // Check whether the list has a loop
        if (head == null || head.next == null || head.next.next == null) return null;
        Node slow = head.next;
        Node fast = head.next.next;
        while(slow ! = fast) {if (fast.next == null || fast.next.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = head;
        while(fast ! = slow) { fast = fast.next; slow = slow.next; }return fast;
    }
Copy the code

3. According to the results of getLoop, we process them according to the categories in 1

1. If two lists do not have a loop, this is the only way they can intersect. This is the noLoop method

2. If both lists have loops, there are two cases of intersection, which correspond to the bothLoop method

3. One of head1 and head2 with and without rings cannot have intersecting nodes

The problem solving skills

The method to get the first entry point

The list has a loop, each time the slow pointer takes one step, the fast pointer takes two steps, the fast pointer and the slow pointer will meet, after meeting, the fast pointer from the beginning takes one step at a time, the slow pointer continues to take one step at a time, where they meet is the first entry point

A method to obtain the intersection of two acyclic linked lists

 public Node noLoop(Node head1, Node head2) {
        int n = 0;
        Node n1 = head1;
        while(n1 ! =null) {
            n1 = n1.next;
            n++;
        }
        Node n2 = head2;
        while(n2 ! =null) {
            n2 = n2.next;
            n--;
        }
        if(n1 ! = n2)return null; // If this is not a common node, it means that two lists do not intersect
        n1 = n > 0 ? head1 : head2;
        n2 = n1 == head1 ? head2 : head1;
        // Let n1 become the long list
        n = Math.abs(n);
        while(n ! =0) {
            n1 = n1.next;
            n--;
        }
        while(n1 ! = n2) { n1 = n1.next; n2 = n2.next; }return n1;
    }
Copy the code

1. First walk through the linked list head1, using n to record the length

2. Traverse the linked list head2. N records the length difference between head1 and head2

3. Let the long list go n steps first, and then the Pointers of the two lists go at the same time until they meet

code

public Node findFirstIntersectNode(Node head1, Node head2) {
        Node loop1 = getLoop(head1);
        Node loop2 = getLoop(head2);
        if (loop1 == null && loop2 == null) {// Big case 1: simultaneous acyclic
            System.out.println("noLoop");
            return noLoop(head1, head2);
        }
        if(loop1 ! =null&& loop2 ! =null) {// Big case 2: both rings
            return bothLoop(head1, head2, loop1, loop2);
        }
        // Big case 3: there is only one case with a ring and one without a ring, and there is no common intersection
        return null;
    }

    public Node bothLoop(Node head1, Node head2, Node loop1, Node loop2) {
        // The first is when both entry points are the same
        if (loop1 == loop2) { // Take the entry point as the end point, and then follow the instructions in noLoop
            int n = 0;
            Node n1 = head1;
            Node n2 = head2;
            while(n1 ! = loop1) { n1 = n1.next; n++; }while(n2 ! = loop1) { n2 = n2.next; n--; } n1 = n >0 ? head1 : head2;
            n2 = n1 == head1 ? head2 : head1;
            n = Math.abs(n);
            while(n ! =0) {
                n1 = n1.next;
                n--;
            }
            while(n1 ! = n2) { n1 = n1.next; n2 = n2.next; }return n1;   // In this case, there must be nodes of intersection
        } else {
            Node n1 = loop1.next;
            while(n1 ! = loop1) {if (n1 == loop2) return loop2;
                n1 = n1.next;
            }
            return null;   // The third is the case where two entry points are not the same, but have the same ring}}public Node noLoop(Node head1, Node head2) {
        int n = 0;
        Node n1 = head1;
        while(n1 ! =null) {
            n1 = n1.next;
            n++;
        }
        Node n2 = head2;
        while(n2 ! =null) {
            n2 = n2.next;
            n--;
        }
        if(n1 ! = n2)return null; // If this is not a common node, it means that two lists do not intersect
        n1 = n > 0 ? head1 : head2;
        n2 = n1 == head1 ? head2 : head1;
        // Make head1 the long list
        n = Math.abs(n);
        while(n ! =0) {
            n1 = n1.next;
            n--;
        }
        while(n1 ! = n2) { n1 = n1.next; n2 = n2.next; }return n1;
    }

    public Node getLoop(Node head) { // Check whether the list has a loop
        if (head == null || head.next == null || head.next.next == null) return null;
        Node slow = head.next;
        Node fast = head.next.next;
        while(slow ! = fast) {if (fast.next == null || fast.next.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = head;
        while(fast ! = slow) { fast = fast.next; slow = slow.next; }return fast;
    }
Copy the code