Ciclo de lista vinculada
Guia detalhado e implementação de Python para o problema do 'Ciclo de lista vinculada'.
1. Aprenda
O problema do 'Ciclo de lista vinculada' é um desafio importante na seção Lista vinculada.
Esta implementação concentra-se na lógica de nível fácil em Python.
Priorizamos a precisão técnica e a legibilidade do código em nossas soluções fornecidas.
2. Real-World Applications
3. Visual Intuition
Visualizando o fluxo lógico do Ciclo de Lista Vinculada.
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
Leia atentamente a definição do problema do Ciclo de lista vinculada.
2. Formulate brute force
Elabore uma solução iterativa simples.
3. Identify inefficiency
Procure cálculos redundantes.
4. Optimize search path
Use hashing ou classificação para acelerar o processo.
5. Final Implementation
Limpe o código para padrões de produção.
Declaração do problema
Dado o cabeçalho, o cabeçalho de uma lista vinculada, determine se a lista vinculada contém um ciclo.
Existe um ciclo em uma lista vinculada se houver algum nó na lista que possa ser alcançado novamente seguindo continuamente o próximo ponteiro. Internamente, pos é usado para denotar o índice do nó ao qual o próximo ponteiro da cauda está conectado. Observe que pos não é passado como parâmetro.
Retorne verdadeiro se houver um ciclo na lista vinculada. Caso contrário, retorne falso.
A entrada é fornecida como uma lista de valores e um número inteiro pos (o índice ao qual a cauda se conecta, -1 se não houver ciclo). Implemente uma função hasCycle(head: list, pos: int) -> bool.
- •The number of nodes in the list is in the range [0, 10000]
- •-100000 <= Node.val <= 100000
- •pos is -1 or a valid index in the linked list
Exemplos
[3,2,0,-4], 1
True
There is a cycle: the tail node (-4) connects back to the node at index 1 (value 2).
[1,2], 0
True
There is a cycle: the tail node (2) connects back to the node at index 0 (value 1).
[1], -1
False
There is no cycle in the list.
Need a Hint?
Edge Cases to Watch
- Estruturas de entrada vazias
- Entradas de elemento único
- Grandes limites numéricos
Pronto para resolver?
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.
Insights e variações da entrevista
Análise de complexidade
Por que tempo: Directly evaluates all possibilities.
Por que espaço: Uses standard local memory.
Por que tempo: Optimized paths reduce total operations.
Por que espaço: May trade memory for speed.
Código Python da solução otimizada
Código Python da solução otimizada
def has_cycle_opt(head, pos=None):
if isinstance(head, list):
if pos is None or pos == -1:
h = build_linked_list(head)
else:
h = build_linked_list(head)
curr = h
cycle_node = None
idx = 0
while curr.next:
if idx == pos:
cycle_node = curr
curr = curr.next
idx += 1
if idx == pos:
cycle_node = curr
curr.next = cycle_node
return has_cycle_opt_helper(h)
return has_cycle_opt_helper(head)
def has_cycle_opt_helper(head: ListNode) -> bool:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return FalseCódigo de força bruta (protegido por spoiler)
Código de força bruta (protegido por spoiler)
def has_cycle_brute(head, pos=None):
if isinstance(head, list):
# Rebuild linked list with a cycle
if pos is None or pos == -1:
h = build_linked_list(head)
else:
h = build_linked_list(head)
curr = h
cycle_node = None
idx = 0
while curr.next:
if idx == pos:
cycle_node = curr
curr = curr.next
idx += 1
if idx == pos:
cycle_node = curr
curr.next = cycle_node
return has_cycle_brute_helper(h)
return has_cycle_brute_helper(head)
def has_cycle_brute_helper(head: ListNode) -> bool:
seen = set()
curr = head
while curr:
if curr in seen:
return True
seen.add(curr)
curr = curr.next
return FalseAlgorithm Pattern Checklist
When dealing with Linked List data patterns.
- Are constraints clear?
- Is there a linear or logarithmic optimization possible?
Key Revision Notes
Aplicam-se propriedades de problema de lista vinculada padrão.
Perguntas relacionadas
PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!
Recursos Python recomendados
Expanda seu conhecimento com tutoriais interativos relacionados, folhas de dicas e comparações de código.
Listas Python
Aprenda tudo sobre listas Python. Descubra como criar, fatiar, modificar e iterar nativamente arrays em Python.
Como classificar uma lista em Python
Aprenda como classificar uma lista em Python usando o método sort() e a função sorted(). Descubra exemplos de classificação de chaves personalizadas e ordem reversa.
Folha de referências de métodos de lista Python
Guia de referência rápida para operações de lista Python. Domine a adição, inserção, remoção, classificação e fatiamento de elementos.
Python vs JavaScript: qual linguagem de programação é a melhor?
Uma comparação abrangente entre Python e JavaScript. Explore diferenças de sintaxe, desempenho, casos de uso (backend versus frontend) e exemplos de codificação.