Hey, guys. I’m balls.

Today, we are going to cut the circular list, which is still a frequent interview question.

Judging circular lists is a little more mentally complicated, but don’t panic, I’m here.

LeetCode 141: Circular linked list

The question

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

The sample

Use the integer pos to represent the position in the list to which the list tail is attached (the index starts at 0).

Enter: head = [3, 2, 0, -4], pos = 1

Output: true,

Explanation: A linked list has a ring whose tail is connected to a second node.

Enter: head = [1], pos = -1

Output: false

Explanation: There are no rings in the linked list.

prompt

  • Pos is not passed as an argument and only identifies the actual condition of the linked list.
  • 0 <= Number of linked list nodes <= 10^4
  • 10^-5 <= Node.val <= 10^5
  • Pos is -1 or a valid index in a linked list.

title

The difficulty is simple, the solution method is odd, in the practical application should not have the brain watt to use this method.

This is a weird way to solve the problem: fast or slow Pointers.

Fast and slow Pointers, as the name suggests, use Pointers with different speeds (used on linked lists, arrays, sequences, etc.) to solve some problems.

These issues mainly include:

  • Handles problems on rings, such as circular lists, circular arrays, etc.
  • When you need to know the length of a linked list or information at a particular location.

The fast and slow pointer algorithm proves that they will definitely meet, and the fast pointer will catch up with the slow pointer, which can be understood as running on the playground, and the fast one will run in a circle and the slow one will run.

Generally, fast is used to define fast Pointers and slow is used to define slow Pointers. Different speed means that fast takes more steps each time and slow takes fewer steps. The general setting is 2 steps for fast and 1 step for slow.

Of course, it is also possible to set it to other integers, such as 3 steps for fast and 1 step for slow.

The illustration

Use the fast or slow pointer in this case:

  • If the list is loopless, the fast pointer will point to Null first.
  • If the list has a ring, fast and slow will meet in the ring sooner or later.

For example, head = [3, 2, 0, -4], pos = 1.

Step 1: Initialize the fast or slow pointer. Slow takes 1 step, fast takes 2 steps.

Initialize the pointer fast = slow = headCopy the code

Step 2: Slow moves 1 step, fast moves 2 steps.

While fast = fast. Next = slow. Next: # fast = fastCopy the code

Step 3: Same as above.

Step 4: Same as above.

At this point, fast = slow, judging that there is a loop, return true, end.

If fast == slow: return TrueCopy the code

Fast and slow pointer

  • Linked lists are loopless and each node is accessed at most 2 times.
  • Lists have loops that move n rounds at most.

So the time is order n.

In addition, only two extra Pointers fast and slow are used, so the space complexity is O(1).

Code implementation

Python code implementation

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): Class Solution: def hasCycle(self, head: ListNode) -> bool: # self.val = x # self.next = None If not head or head. Next == None: Return False # initialize the fast = slow = head pointer # if there is no loop, it must be null # details: Fast takes two steps at a time, so make sure that fast and fast.next are not empty, otherwise an execution error will be reported. While fast == fast. Next: # if fast == slow: return True return FalseCopy the code

Java code implementation

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; *} *} */ # 微信 号 : */ public class Solution {public Boolean hasCycle(ListNode head) {if(head==null) return false; ListNode fast=head.next; ListNode slow=head; while(fast! =null&&fast.next! =null) { fast=fast.next.next; // slow=slow. Next; If (fast==slow) return true; if(fast==slow) return true; } return false; }}Copy the code

Is there a link that ends here? Isn’t that hard?

Carefully try to figure out, pay attention to the details of the code, more practice more knock can be invincible, smelly treasure refueling.

Don’t forget my thumbs up, more content welcome to pay attention to the public number [programming Wenqing Li Guodan], unlock more data structures and algorithms.

I’m Handsome. I’ll see you next time.