141. Ring linked list | brush question punch

create by db on 2021-3-13 13:00:44

Recently revised in 2021-3-13 13:10:48

Idle time to have a tight mind, busy time to have leisure fun

141. Circular list > Table of contents

  • Topic describes
  • Thought analysis
  • AC code
  • conclusion

Topic describes

Returns the directory

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 the list ranges from 0 to 104.
  • -105 <= Node.val <= 105
  • Pos is -1 or a valid index in a linked list

Thought analysis

Another linked list problem.

Idea 1: Hash table

The easiest way to think about it is to go through all the nodes and store them; Each time you traverse to the next node, determine whether the node has been accessed before.

Specifically, we can use a hash table (Map) to store all nodes that have been visited. Every time we reach a node, if it already exists in the hash table, it is a circular list, otherwise it is added to the hash table. Repeat this process until we have traversed the entire list.

Complexity analysis

  • Time complexity: O(N), where N is the number of nodes in the linked list. In the worst case we need to traverse each node once.

  • Spatial complexity: O(N), where N is the number of nodes in the linked list. Mostly hash table overhead, in the worst case we need to insert each node into the hash table once.

Idea 2: fast and slow pointer

This method requires readers to have some knowledge of “Floyd loop detection algorithm” (also known as the tortoise and rabbit racing algorithm).

Imagine turtles and rabbits moving on a linked list, with rabbits running fast and turtles slow. When the tortoise and the rabbit start from the same node on the list, if there are no rings in the list, the rabbit will always be in front of the tortoise. If there are rings in the list, the rabbit enters the ring before the tortoise and moves through it all the time. Wait until the “tortoise” into the ring, because of the “rabbit” speed, it will meet at a certain moment with the tortoise, namely set the “tortoise” several circles.

We can solve the problem according to the above thought. Specifically, we define two Pointers, one fast and one full. The slow pointer moves one step at a time while the fast pointer moves two steps at a time. Initially, the slow pointer is in position head and the fast pointer is in position head.next. In this way, if the fast pointer catches up with the slow pointer as it moves, the list is a circular list. Otherwise, the fast pointer will reach the end of the list, which is not a circular list.

AC code

Solution 1: Hash table

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} head
 * @return {boolean}* /
var hasCycle = function (head) {
  // Non-null judgment
  if(! head || ! head.next) {return false
  }
  / / a hash table
  let dataMap = new Map(a)while (head) {
    if (dataMap.has(head)) {
      return true
    }
    dataMap.set(head, 1)
    head = head.next
  }
  return false
}
Copy the code

Solution 2: Fast and slow pointer

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} head
 * @return {boolean}* /
var hasCycle = function (head) {
  // Non-null judgment
  if(! head || ! head.next) {return false
  }
  // Define a pointer
  let slow = head
  let fast = head.next
  while(slow ! == fast) {if(! fast || ! fast.next) {return false
    }
    slow = slow.next
    fast = fast.next.next
  }
  return true
}
Copy the code

conclusion

Returns the directory

March hello, spring flowers. Come on!

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign

Postscript: Hello friends, if you think this article is good, remember to give a thumbs-up or star, your thumbs-up and star is my motivation to write more and richer articles!Making the address

Document agreement



dbThe document library 由 dbusingCreative Commons Attribution – Non-commercial Use – Same way Share 4.0 International LicenseGrant permission.

Based on thegithub.com/danygitgitOn the creation of works.

Use rights other than those authorized by this License agreement may be obtained fromCreativecommons.org/licenses/by…Obtained.