141. Circular linked list

Clock in !!! A daily topic

Today I want to share with you a topic of linked list type , The subject is very simple , It is mainly the method of treatment , There are two main questions in this paper , Take you from the first question to the second question .

subject 1：141. Circular list

Title Description ：

Give you a list of the head node head , Judge whether there are links in the list .

If there is a node in the linked list , It can be done by continuously tracking next The pointer reaches again , Then there is a ring in the linked list . To represent a ring in a given list , The evaluation system uses an integer pos To indicate where the end of the list is connected to the list （ Index from 0 Start ）. Be careful ：pos Not passed as an argument . Just to identify the actual situation of the linked list .

If there are rings in the list , Then return to true . otherwise , return false .

Title Example ：

Let's simply analyze this problem , The meaning of the topic is very simple , Is to let you judge whether there is a ring , Our approach is also very simple , Save the nodes we have traversed , Once a node is found Next Have been interviewed , Description ring , If the linked list traversal ends, there is no ring .

Conditions for the end of traversal ：

• 1. End of traversal , That is to say, the next It's empty .
• 2. Traverse to the node that has been visited .

    public boolean hasCycle(ListNode head) {
    
        if(head==null)return false;
        List<ListNode>list=new ArrayList<>();
        while(!list.contains(head)&&head!=null){
    
            list.add(head);
            head=head.next;
        }
        if(head==null){
    
            return false;
        }else return true;
    }

Is it simple , Let's continue to think about an advanced problem .

subject 2：142. Circular list 2

Title Description ：

Given the head node of a linked list head , Return to the first node of the link where the list begins to enter . If the list has no links , Then return to null.

If there is a node in the linked list , It can be done by continuously tracking next The pointer reaches again , Then there is a ring in the linked list . To represent a ring in a given list , The evaluation system uses an integer pos To indicate where the end of the list is connected to the list （ Index from 0 Start ）. If pos yes -1, There are no links in the list . Be careful ：pos Not passed as an argument , Just to identify the actual situation of the linked list .

No modification allowed Linked list .

Title Example ：

This question and The last question is basically the same , The only difference is that we need to return the first node of the linked list to enter the ring .

The key to this problem is to find which node next Was visited , Once found , We directly return that will do .

    public ListNode detectCycle(ListNode head) {
    
        if(head==null||head.next==null)return null;
        List<ListNode>list=new ArrayList<>();
        while(!list.contains(head)&&head!=null){
    
            list.add(head);
            if(list.contains(head.next)){
    
                return head.next;
            }
            head=head.next;
        }
        return null;
    }