Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2:
Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Example 3:
Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.
Constraints:
[0, 104].-105 <= Node.val <= 105pos is -1 or a valid index in the linked-list.Follow up: Can you solve it using O(1) (i.e. constant) memory?
program main
implicit none
type :: Node
integer :: val
type(Node), pointer :: next => null()
end type
type(Node), target :: head
type(Node), pointer :: current
logical :: has_cycle
! Example 1
allocate(current, source=Node(3))
allocate(current%next, source=Node(2))
allocate(current%next%next, source=Node(0))
allocate(current%next%next%next, source=Node(-4))
has_cycle = hasCycle(head)
print '(L1)', has_cycle
! Example 2
deallocate(current)
allocate(current, source=Node(1))
allocate(current%next, source=Node(2))
has_cycle = hasCycle(head)
print '(L1)', has_cycle
! Example 3
deallocate(current)
allocate(current, source=Node(1))
has_cycle = hasCycle(head)
print '(L1)', has_cycle
contains
function hasCycle(head) result(has_cycle)
type(Node), target :: head
type(Node), pointer :: current
integer :: pos
current => head
pos = 1
do while (associated(current%next))
if (pos == current%next%val) then
has_cycle = .true.
exit
end if
current => current%next
pos = current%val
end do
has_cycle = .false.
end function
end programtemp.f95:36:45:
36 | function hasCycle(head) result(has_cycle)
| 1
Error: Function result ‘has_cycle’ at (1) has no IMPLICIT type
temp.f95:18:16:
18 | has_cycle = hasCycle(head)
| 1
Error: Cannot convert UNKNOWN to LOGICAL(4) at (1)
temp.f95:25:16:
25 | has_cycle = hasCycle(head)
| 1
Error: Cannot convert UNKNOWN to LOGICAL(4) at (1)
temp.f95:31:16:
31 | has_cycle = hasCycle(head)
| 1
Error: Cannot convert UNKNOWN to LOGICAL(4) at (1)
module linked_list_cycle
implicit none
contains
function has_cycle(head) result(cycle)
! Given the head of a linked list, determine if the linked list has a cycle in it.
! Return true if there is a cycle, false otherwise.
! head: the head of the linked list
! cycle: true if there is a cycle, false otherwise
type(node), pointer :: head
logical :: cycle
! Initialize the cycle flag to false
cycle = .false.
! If the list is empty, there is no cycle
if (associated(head)) then
! If the list has only one node, there is no cycle
if (associated(head%next)) then
! If the list has more than one node, check for a cycle
cycle = has_cycle_helper(head)
end if
end function has_cycle
recursive function has_cycle_helper(node) result(cycle)
! Given a node in a linked list, determine if the linked list has a cycle in it.
! Return true if there is a cycle, false otherwise.
! node: the node to check for a cycle
! cycle: true if there is a cycle, false otherwise
type(node), pointer :: node
logical :: cycle
! If the node is null, there is no cycle
if (.not. associated(node)) then
cycle = .false.
return
end if
! If the node's next pointer is null, there is no cycle
if (.not. associated(node%next)) then
cycle = .false.
return
end if
! If the node's next pointer points back to the node, there is a cycle
if (node%next == node) then
cycle = .true.
return
end if
! Recursively check the next node in the list
cycle = has_cycle_helper(node%next)
end function has_cycle_helper
end module linked_list_cycle
program test
use linked_list_cycle
implicit none
! Test case 1:
type(node), pointer :: head
integer :: i
! Create a linked list with a cycle
do i = 1, 4
head = new_node(i)
end do
head%next%next%next = head
! Check if the linked list has a cycle
if (has_cycle(head)) then
write (*,*) "Linked list has a cycle"
else
write (*,*) "Linked list does not have a cycle"
end if
! Test case 2:
head = new_node(1)
head%next = new_node(2)
! Check if the linked list has a cycle
if (has_cycle(head)) then
write (*,*) "Linked list has a cycle"
else
write (*,*) "Linked list does not have a cycle"
end if
! Test case 3:
head = new_node(1)
! Check if the linked list has a cycle
if (has_cycle(head)) then
write (*,*) "Linked list has a cycle"
else
write (*,*) "Linked list does not have a cycle"
end if
contains
type(node), pointer function new_node(value)
! Create a new node with the given value
! value: the value to store in the node
integer, intent(in) :: value
type(node), pointer :: new_node
allocate(new_node)
new_node%value = value
new_node%next => null()
end function new_node
end program test
temp.f95:15:11:
15 | type(node), pointer :: head
| 1
Error: Derived type ‘node’ at (1) is being used before it is defined
temp.f95:25:21:
25 | if (associated(head%next)) then
| 1
Error: Symbol ‘head’ at (1) has no IMPLICIT type
temp.f95:42:11:
42 | type(node), pointer :: node
| 1
Error: Derived type ‘node’ at (1) is being used before it is defined
temp.f95:52:27:
52 | if (.not. associated(node%next)) then
| 1
Error: Symbol ‘node’ at (1) has no IMPLICIT type
temp.f95:55:3:
55 | end if
| 1
Error: Expecting END FUNCTION statement at (1)
temp.f95:58:10:
58 | if (node%next == node) then
| 1
Error: Symbol ‘node’ at (1) has no IMPLICIT type
temp.f95:61:3:
61 | end if
| 1
Error: Expecting END FUNCTION statement at (1)
temp.f95:64:6:
64 | cycle = has_cycle_helper(node%next)
| 1
Error: Syntax error in CYCLE statement at (1)
temp.f95:7:23:
7 | function has_cycle(head) result(cycle)
| 1
Error: Symbol ‘head’ at (1) has no IMPLICIT type
temp.f95:34:40:
34 | recursive function has_cycle_helper(node) result(cycle)
| 1
Error: Symbol ‘node’ at (1) has no IMPLICIT type
temp.f95:72:5:
72 | use linked_list_cycle
| 1
Fatal Error: Cannot open module file ‘linked_list_cycle.mod’ for reading at (1): No such file or directory
compilation terminated.
def hasCycle(head):
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
The algorithm used is Floyd's cycle-finding algorithm, also known as the "tortoise and the hare" algorithm. There are two pointers, one slow (tortoise) and another fast (hare). The slow pointer moves one step at a time, and the fast pointer moves two steps.
Initially, both pointers are set to the head of the linked list. The pointers are moved forward with their respective speeds until either the fast pointer reaches the end of the linked list or both pointers meet at the same node.
If the fast pointer reaches the end, it means that there is no cycle and the function returns false. If the pointers meet at some point in the linked list, there is a cycle and the function returns true.
bool hasCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return true;
}
}
return false;
}
The algorithm used is Floyd's cycle-finding algorithm, also known as the "tortoise and the hare" algorithm. There are two pointers, one slow (tortoise) and another fast (hare). The slow pointer moves one step at a time, and the fast pointer moves two steps.
Initially, both pointers are set to the head of the linked list. The pointers are moved forward with their respective speeds until either the fast pointer reaches the end of the linked list or both pointers meet at the same node.
If the fast pointer reaches the end, it means that there is no cycle and the function returns false. If the pointers meet at some point in the linked list, there is a cycle and the function returns true.