“This is the fourth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

[B] [C] [D]

1244 Switch to English to receive dynamic feedback

Given a linked list, determine whether there are rings in the list.

If there is a node in the list that can be reached again by following the next pointer continuously, then there is a ring in the list. To represent the rings in a given list, we use the integer pos to represent where in the list the tail joins (the index starts at 0). If pos is -1, there are no rings in the linked list. Note: POS is not passed as an argument, just to identify the actual state of the linked list.

Returns true if there are rings in the list. Otherwise, return false.

Advanced:

Can you solve this problem with O(1) (i.e., constant) memory?

Example 1:

Input: head = [3,2,0,-4], pos = 1 output: true explanation: there is a ring in the linked list whose tail is connected to a second node.Copy the code

Example 2:

Input: head = [1,2], pos = 0 output: true explanation: there is a ring in the linked list whose tail is connected to the first node.Copy the code

Example 3:

Input: head = [1], pos = -1 Output: false Explanation: There are no loops in the linked list.Copy the code

Tip:

  • The number of nodes in a linked list ranges from[0, 104]
  • -105 <= Node.val <= 105
  • pos 为 - 1Or one of the linked listsEffective index 。

1.

  1. First, judge ifheadIs empty orhead.nextIs null, there must be no ring at this point, returnfalse
  2. Loop list nodes if there are no current list nodestagProperty to define the current nodetagProperty to indicate that the node has been visited, if the current node hastagProperty, indicating that we have visited the node before, and then come to the node again to prove that the node has a ring, returntrue
  3. If I go through the entire list and I don’t see anytagProperty to prove that the list has no rings, returnsfalse

The code is as follows:

var hasCycle = function(head) {
    if(head === null || head.next===null) return false;
    let cur = head;
    while(cur){
        if(cur.tag) return true;
        else{
            cur.tag = 'a'
            cur = cur.next;
        }
    }
    return false;
};
Copy the code

2.

  1. Define two fast and slow Pointerspre 和 nextInitializing all points tohead
  2. whennextNot empty andnext.nextDon’t empty,nextTake one step back at a time,preTake two steps back at a time
  3. If there are rings in the linked list, thenpre 和 nextWill meet at the beginning of the ring and returntrue. Otherwise, if you go to the end of the list,nextornext.nextWill pointnullTo return tofalse

The code is as follows:

var hasCycle = function(head) {
    if(head === null || head.next===null) return false;
    let cur = head;
    while(cur){
        if(cur.tag) return true;
        else{
            cur.tag = 'a'
            cur = cur.next;
        }
    }
    return false;
};
Copy the code

At this point we have completed the Leetcode-141-ring linked list

If you have any questions or suggestions, please leave a comment!