The title

LeetCode 第 141. Association types: linked lists, double Pointers

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.Copy the code

Time to solve the problem.

/**
 * 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) {
      
      
    }
}
Copy the code

The method input parameters are given above to complete the answer.

Subject analysis

  1. Use the idea of fast and slow pointer to solve the problem
  2. We define two Pointers, one fast and one slow.
  3. The slow pointer moves one step at a time while the fast pointer moves two steps at a time.
  4. 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.

Answers to analysis

This article only analysis I do the idea, only for reference, to understand a solution to the idea, other kinds of ideas to do the problem please access the Internet.

Answer successful: Execution time :0 ms, beat 100.00% Java user memory consumption :39.6 MB, beat 38.10% Java user

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head==null){
            return false;
        }
        ListNode fastNode = head;
        ListNode slowNode = head;
        while (fastNode.next != null) {
            fastNode = fastNode.next.next;
            slowNode = slowNode.next;
            if (fastNode == null) {
                return false;
            } else if (fastNode == slowNode) {
                return true;
            }
        }
        return false;
    }
}
Copy the code