I. Title Description:

Leetcode 第141题 : Circular linked lists

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

Ii. Analysis of Ideas:

Solution 1: Violence

Set two Pointers cur1 and cur2

  • Each time CUR1 traverses a node, cur2 traverses all previous nodes from the beginning
  • If CUR2 goes to Cur1 in the same number of steps, then the meeting point is not the entry point
  • If cur2 goes to Cur1 in different steps, then the encounter point is the entry point, and Cur1 goes one more loop than Cur2

Complexity analysis Time complexity: O(n^2), where n is the number of elements in the linked list. Space complexity: O(1), no additional space overhead.

Solution 2: With the help of hash table, mark judge weight

By virtue of the fast query time of hash table, we create a hash Map. Each time a linked list node is traversed, the hash table is checked to see if the current node exists. If so, the linked list has a ring. If it doesn’t exist, store it in the hash table and continue iterating. Complexity analysis Time complexity: O(n), where N is the number of elements in the linked list. This method traverses the linked list node once, and the time complexity is N. The hash table queries whether the node exists, and the time complexity is 1, so the comprehensive time complexity is N. Space complexity: O(n), hash table is extra space consumption.

Solution 3: Fast and slow pointer

Set the fast and slow Pointers

  • Fast and slow Pointers, starting from the beginning node
  • Slow Pointers take one step at a time and fast Pointers take two steps at a time, constantly comparing the values of the nodes they point to
  • If the values of the nodes are the same, there are rings. If not, continue the loop.

Similar to “catch and the problem” : two people in a ring track race, starting from the same starting point, one runs fast and one runs slow, at a certain moment, the faster will catch up with the slower, as long as the track is circular, not circular can certainly not catch up.

Complexity analysis Time complexity: O(n) Space complexity: O(1)

Iii. AC Code:

Code for brute force law

var hasCycle = (head) => { let cur1 = head; // let step1 = 0; While (cur1) {step1++; let cur2 = head; // let step2 = 0; While (cur2) {step2++; If (step1 == step2) {// if (step1 == step2) {// if (step1 == step2) {// if (step1 == step2) {// if (step1 == step2) {// if (step1 == step2) {// if (step1 == step2) {// if (step1 == step2) {// if (step1 == step2) { // Exit the inner layer while} else {return true; // Indicates that the linked list has rings. }} cur2 = cur2.next; } cur1 = cur1.next; // cur1 step at a time} return false; };Copy the code

With the help of a hash table, mark the code for weighting

var hasCycle = (head) => {
  let map = new Map();
  while(head) {
    if(map.has(head)) return true;
    map.set(head, true);
    head = head.next;
  }
  return false;
}
Copy the code

Fast or slow pointer code

var hasCycle = function(head) { if(! head || ! head.next) { return false } let slow = head; let fast = head.next; while(fast ! == null && fast.next) { slow = slow.next; fast = fast.next.next; if(slow === fast) { return true; } } return false; };Copy the code

Iv. Summary:

Solution 2 continues to borrow the idea of space for time learned on the first day, while solution 3 further optimizes the spatial complexity on the basis of solution 2. Therefore, writing high quality code with high execution efficiency requires constant internal training! Tomorrow continue to brush ~~

This article is participating in the “Gold Digging march Campaign”, click to see the details of the campaign