This is the fifth day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the 38th day 🎈!
🚀 Algorithm 🚀

🌲 Example: Circular linked list

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.

Example 1: 

Enter: head = [3.2.0.4 -], pos = 1Output:trueExplanation: A linked list has a ring whose tail is connected to a second node.Copy the code

Example 2: 

Enter: head = [1.2], pos = 0Output:trueExplanation: A linked list has a ring whose tail is connected to the first node.Copy the code

Example 3:

Enter: head = [1], pos = - 1Output:falseExplanation: There are no rings 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

🌻C# method: double pointer

Thinking analytical

The fast and slow Pointers start at the same time from the beginning of the node. The fast Pointers take two steps at a time, and the slow Pointers take one step at a time. If there is a loop, the fast Pointers catch up with the slow Pointers sooner or later.

Code:

public class Solution {
public bool HasCycle(ListNode head)
        {
            ListNode slow = head;
            ListNode fast = head;

            while(fast ! =null&& fast.next ! =null)
            {
                slow = slow.next;
                fast = fast.next.next;
                if(slow == fast)
                {
                    return true; }}return false; }}Copy the code

The execution result

By execution time:92Ms, in all C# beat 74.50% of users in submissionMemory consumption:26.6MB, in all C# beat 75.17% of users in submission
Copy the code

🌻Java method: hash table

Thinking analytical

The easiest way to think about it is to traverse all the nodes, and each time you traverse a node, determine whether it has been accessed before.

Specifically, we can use a hash table to store all nodes that have been accessed. 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.

Code:

class Solution {
    public boolean isPalindrome(String s) {
        StringBuffer sgood = new StringBuffer();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (Character.isLetterOrDigit(ch)) {
                sgood.append(Character.toLowerCase(ch));
            }
        }
        StringBuffer sgood_rev = new StringBuffer(sgood).reverse();
        returnsgood.toString().equals(sgood_rev.toString()); }}Copy the code

The execution result

By execution time:4Ms, beat out all Java commits20.23% user memory consumption:39.1MB, beat out all Java commits83.75% of the userCopy the code

Complexity analysis

Time complexity: O(N), where N is the number of nodes in the linked list Space complexity: O(N), where N is the number of nodes in the linked listCopy the code

💬 summary

  • Today is the thirty-eighth day of clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!