Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Circular linked list I

The title

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, complete with O(1) memory space

Train of thought

1. The fast and slow Pointers are circular if fast and slow can meet; if fast and slow cannot meet, they must be null first

code

public class Solution {
    public boolean hasCycle(ListNode head) {

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

Circular linked list II

The title

Given a linked list, return the first node where the list begins to loop. Returns NULL if the list is loopless.

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 that pos is only used to identify the case of the ring and is not passed to the function as an argument.

Note: Modification of a given linked list is not allowed.

Advanced:

Can you use O(1) space to solve this problem?

Source: LeetCode

Train of thought

II and I add a search entry requirement to the base

1. Define a fast pointer that moves two steps at a time, and a slow pointer that moves one step at a time (both initially point to head)

2. The first while loop makes the fast pointer and slow meet (jump out when they meet)

3. After the encounter, the fast pointer starts to take a step again, and the slow pointer continues to take a step in the original position, and the place where it meets again is the first node of the ring

Key: fast and slow pointer, meet after the fast pointer from the beginning, two Pointers a step to meet again is the entrance

code

public class Solution {
    public ListNode detectCycle(ListNode head) {
        // The speed pointer

        ListNode fast = head;
        ListNode slow = head;
        while (true) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        fast = head;  // Let the fast pointer start over, one step at a time
        while(fast ! = slow) { fast = fast.next; slow = slow.next; }returnfast; }}Copy the code