Welcome to Subscribe On Youtube
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
-
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; } } }
-
// OJ: https://leetcode.com/problems/linked-list-cycle/ // Time: O(N) // Space: O(1) class Solution { public: bool hasCycle(ListNode *head) { ListNode *p = head, *q = head; while (q && q->next) { p = p->next; q = q->next->next; if (p == q) return true; } return false; } };
-
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: ListNode) -> bool: slow = fast = head while fast and fast.next: slow, fast = slow.next, fast.next.next if slow == fast: return True return False ############ # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ fast = slow = head while fast and fast.next: fast = fast.next.next slow = slow.next if slow == fast: return True return False