← all entries
A-041● Day 412026.06.16easyleetcode #141neetcode150

Linked List Cycle

#hash-table#linked-list#two-pointers
↗ leetcode #141 · linked-list-cycle
01

Problem

· problem
P.041

Linked List Cycle

↗ leetcode #141

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.

constraints
  • · 0 ≤ number of nodes ≤ 10^4
  • · -10^5 ≤ node.val ≤ 10^5
  • · pos is -1 or a valid index in the linked list
// paraphrased summary — see source for full text
examples
example 1input → output
[3,2,0,-4]
1
true
example 2input → output
[1,2]
0
true
example 3input → output
[1]
-1
false
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    Is the position parameter (pos) given as an input to the function?
  • ☐
    If there is no space constraint, can we use a hash table or set to store visited nodes?
  • ☐
    Can the linked list be empty (head is null)?
  • ☐
    Can there be multiple nodes before entering the cycle?
  • ☐
    Can we modify node values or mark visited nodes?
  • ☐
    Is it mathematically guaranteed that if the fast pointer catches the slow pointer, a cycle exists?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize pointers
○
slow, fast = head, head
○
slow, fast = head, head.next
○
slow = head; fast = None
step 2· Check loop condition
○
while fast and fast.next:
○
while fast:
○
while fast and fast.next and slow:
step 3· Move slow pointer (1 step)│ nested
○
slow = slow.next
○
slow = slow.next.next
○
slow = slow.next if slow else head
step 4· Move fast pointer (2 steps)│ nested
○
fast = fast.next.next
○
fast = fast.next
○
fast = fast.next.next.next
step 5· Check if pointers meet│ nested
○
if slow == fast:
○
if slow.val == fast.val:
○
if slow == fast and slow != head:
step 6· Return final result
○
return False
○
return True
○
return slow == fast
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
# Definition for singly-linked list.
2
# class ListNode:
3
#     def __init__(self, x):
4
#         self.val = x
5
#         self.next = None
6
7
8
class Solution:
9
    def hasCycle(self, head: ListNode) -> bool:
10
        slow, fast = head, head
11
12
        while fast and fast.next:
13
            slow = slow.next
14
            fast = fast.next.next
15
            if slow == fast:
16
                return True
17
        return False
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[3,2,0,-4]
1
→
true
case 2
[1,2]
0
→
true
case 3
[1]
-1
→
false
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.