current position:Home>The intersection problem of single linked list with or without ring

The intersection problem of single linked list with or without ring

2022-01-26 23:24:58 Monday Pro

On the problem of finding the intersection of cyclic and acyclic single linked lists , It is one of the top two problems in the linked list type problem , Let's listen together .

One 、 Title Description

Given two single linked lists that may or may not have rings , Head node head1 and head2.

Please implement a function , If two linked lists intersect , Please return to the first node of the intersection . If they don't intersect , return null

requirement : If the sum of the lengths of two lists is N, Time complexity, please reach O(N), Please reach O(1).

Two 、 Ideas

The solution is divided into two big steps :

(1) Find the loop entry node of the single linked list , Acyclic returns null

(2) According to the ring entry node of the obtained linked list , Then discuss

1、 Find the loop entry node of the single linked list , Acyclic returns null

(1) Traverse this single linked list , If the node traversed at a time is null, Then the single linked list must be acyclic

(2) Otherwise there is a ring

Prepare a quick pointer , A slow pointer . At the beginning of the , Both pointers start at the beginning of the node , The fast pointer goes two nodes at a time , The slow pointer goes one node at a time , Until the two hands meet .

here , Fast pointer and start from the node , One node at a time ; The slow pointer continues down from where it meets , Still go one node at a time , When the two pointers meet again, the node is the ring in node .

2、 According to the ring entry node of the obtained linked list , Then discuss

(1) There are no links in both lists

Traverse one of the linked lists , Record the length of the linked list length1 And the last node end1; Traverse another linked list , Record the length of the linked list length2 And the last node end2.

If end1 and end2 Unequal , Then the two linked lists must not intersect ; otherwise , Calculation length1 and length2 The difference between the a, Long list go first a Nodes , Then two linked lists go down one by one , The first equal node is the first node that intersects .

image.png

(2) One has a ring 、 An acyclic

In this case, two linked lists cannot intersect .( You can try to make up such a structure , Remember a little , It's a single chain table

(3) Both lists have rings

There are three situations , Each has a ring but does not intersect ; The entry node is the same ; There are two nodes in the loop .

1) Each has a ring but does not intersect

image.png

2) The entry node is the same

image.png

3) There are two nodes in the loop

image.png

The entry nodes of the two linked lists are equal : That is, the nodes entering the ring are the same , The solution process is the same as that of two linked lists which are acyclic and intersecting , That is, the following rings can be completely ignored when solving .

The ring nodes of the two linked lists are not equal : Is the first race or the third race . here , Start with one of the looping nodes , Traverse a circle , If you encounter the second entry node when you return to yourself , Is the third kind , Otherwise, it's the first race .

3、 ... and 、 Refer to code for details

1、 Find the loop entry node of the single linked list

/**
 *  Find the loop entry node of the single linked list , Acyclic returns null
 *
 * @author Java And algorithm learning : Monday 
 */
public static Node getLoopNode(Node head) {
    if (head == null || head.next == null || head.next.next == null) {
        return null;
    }
    //  Quick pointer 
    Node fast = head.next.next;
    //  Slow pointer 
    Node slow = head.next;
    while (fast != slow) {
        //  If a fast pointer goes empty , Then the single linked list must be acyclic 
        if (fast.next == null || fast.next.next == null) {
            return null;
        }
        fast = fast.next.next;
        slow = slow.next;
    }

    //  When the fast and slow hands meet , The fast pointer starts from the node again 
    fast = head;
    while (fast != slow) {
        //  At this time, it is no longer necessary to judge that it is empty , If you can get here, the single linked list must be ring 
        //  At this point, the fast pointer goes one node at a time 
        fast = fast.next;
        //  The slow pointer still goes one node at a time 
        slow = slow.next;
    }

    return slow;
}

2、 According to the ring entry node of the obtained linked list , Then discuss

(1) There are no links in both lists

/**
 *  Now we know that the two linked lists are acyclic , Find their first intersection 
 *
 * @author Java And algorithm learning : Monday 
 */
public static Node noLoop(Node head1, Node head2) {
    if (head1 == null || head2 == null) {
        return null;
    }

    Node current1 = head1;
    Node current2 = head2;
    int n = 0;
    //  The linked list is traversed once to get the length 、 The last node 
    while (current1.next != null) {
        n++;
        current1 = current1.next;
    }

    //  The linked list is traversed twice to get the length difference 、 The last node 
    while (current2.next != null) {
        n--;
        current2 = current2.next;
    }

    //  If the last node of two linked lists is not equal , Then it must not intersect 
    if (current1 != current2) {
        return null;
    }

    //  The head node of the long linked list is current1
    current1 = n > 0 ? head1 : head2;
    //  The head node of the short linked list is current2
    current2 = current1 == head1 ? head2 : head1;

    n = Math.abs(n);
    //  Long list go first n Nodes 
    while (n != 0) {
        n--;
        current1 = current1.next;
    }

    //  Two linked lists go down one by one , The first equal node is the first intersecting node 
    while (current1 != current2) {
        current1 = current1.next;
        current2 = current2.next;
    }

    return current1;
}

(3) Both lists have rings

/**
 *  Both lists have rings 
 *  There are three situations , Each has a ring but does not intersect ; The entry node is the same ; There are two nodes in the loop      
 *
 * @author Java And algorithm learning : Monday 
 */
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
    Node current1 = null;
    Node current2 = null;
    if (loop1 == loop2) {
        current1 = head1;
        current2 = head2;
        int n = 0;
        //  Calculation head1 How many nodes are there in the linked list 
        while (current1 != loop1) {
            n++;
            current1 = current1.next;
        }

        //  Calculate the difference between the number of nodes in the two linked lists 
        while (current2 != loop2) {
            n--;
            current2 = current2.next;
        }

        //  The head node of the long linked list is current1
        current1 = n > 0 ? head1 : head2;
        //  The head node of the short linked list is current2
        current2 = current1 == head1 ? head2 : head1;

        n = Math.abs(n);
        //  Long list go first n Nodes 
        while (n != 0) {
            current1 = current1.next;
            n--;
        }

        //  Two linked lists go down one by one , The first equal node is the first intersecting node 
        while (current1 != current2) {
            current1 = current1.next;
            current2 = current2.next;
        }

        return current1;
    } else {
        //  The ring nodes of the two linked lists are not equal , Each has a ring but does not intersect, or there are two nodes entering the ring 
        current1 = loop1.next;
        //  Start with one of the looping nodes , Traverse a circle , If you encounter the second entry node when you return to yourself , It is   There are two nodes in the loop 
        while (current1 != loop1) {
            if (current1 == loop2) {
                //  At this time, the two loop nodes are the first intersection node , Just return one of them 
                return loop1;
            }
            current1 = current1.next;
        }
        return null;
    }
}

The above is the core detailed reference code , I believe that the main method and test method can be written easily , Of course, I want to refer to all the codes , Also attached here is the code for all of this article Github Address :

https://github.com/monday-pro...

copyright notice
author[Monday Pro],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/01/202201262324534851.html

Random recommended