Linked List Cycle Problems - Given a linked list, determine whether there are rings/circle in the linked list.

Linked List Cycle Problems - Given a linked list, determine whether there are rings/circle in the linked list.

Title description:
Given a linked list, determine whether there are rings in the linked list.
In order to represent the rings in a given linked list, we use the integer pos to indicate the position where the tail of the linked list is connected to the linked list (the index starts at 0). If pos is -1, there is no ring in the list.

Map set solution
Idea:
Create a map collection, key is the node, and value is the address value. Because ListNode does not rewrite the toString() method, the content returned by the toString() method is used as the value.
If there is content returned by the toString() method of the current node in the map, there is a ring.

/**
 * 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;
        }
        Map<ListNode,String> map = new HashMap<ListNode,String>();
        while(head != null){
            if(map.containsValue(head.toString())){
                return true;
            }
            else{
                map.put(head,head.toString());
                head = head.next;
            }
        }
        return false;
    }
}
Screenshot of submission result:

Fast and slow pointer solution

Analysis:
point the slow pointer to the head; point
the fast pointer to the head.next;
slow one step in the loop, fast two steps, if there is a ring, then slow and fast will definitely meet, as in this example: slow is 1 At this point, fast is at 2; then slow goes one step to 2, and fast takes two steps to 4; slow to 3, fast to 3, and slow and fast meet.
code show as below:

/**
 * 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 slow = head;
        ListNode fast = head.next;
        while(fast != null){
            if(slow == fast){
                return true;
            }
            slow = slow.next;
            fast = fast.next;
            if(fast != null)
                fast = fast.next;
        }
        return false;
    }
}
Interpretation of the code:
1, if the head is empty, is not a ring, returns to false;
2, if the fast is not empty, the process proceeds to the loop; otherwise exit the loop, acyclic, returns to false;
. 3, if the slow and fast directed If the nodes are the same, there is a ring, which returns true;
4. Slow moves a node backward;
4. Fast moves a node backward. If fast is not empty, moves a node backward (you cannot move two nodes directly, otherwise it will Report null pointer exception);

It can be seen from the figure that the fast and slow pointer method is better.