Question

Formatted question description: https://leetcode.ca/all/141.html

141	Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

@tag-linkedlist

Algorithm

Two pointers, a slow pointer that walks one step at a time and a fast pointer that walks two steps at a time. If there is a ring in the linked list, the two pointers will definitely meet at the same position eventually.

Or, use a set for duplicate check.

Code

Java

import java.util.HashSet;
import java.util.Set;

public class Linked_List_Cycle {

	/**
	 * 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;

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

            return false;
        }
    }

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

	        Set<ListNode> hs = new HashSet<ListNode>();

	        ListNode current = head;

	        while (current != null) {

	            if (hs.contains(current)) {
	                return true;
	            }

	            hs.add(current);
	            current = current.next;
	        }

	        return false;

	    }
	}

}

All Problems

All Solutions