Middle Of The Linked List - LeetCode

📝 Descrição

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

📌 Exemplos

Exemplo 1

Entrada

head = [1,2,3,4,5]

Saída

[3,4,5]

✅ Casos de teste

Caso 1

Entrada

[1,2,3,4,5,6]

Saída

[4,5,6]

🚀 Como resolvi?

Para descobrir o meio de uma lista podemos utilizar física!

Distância percorrida pelo fast:

$$d_{\text{fast}}=v_{\text{fast}}\cdot t=2t$$

Distância percorrida pelo slow:

$$d_{\text{slow}}=v_{\text{slow}}\cdot t=t$$

Como o fast percorreu a lista inteira, temos:

$$2t=L\Rightarrow t=\frac{L}{2}$$

Portanto:

$$d_{\text{slow}}=\frac{L}{2}$$

Ou seja, o slow estará no meio da lista.

🛠️ Implementação

class Solution:
	def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
		slow = fast = head
		while fast and fast.next:
			fast = fast.next.next
			slow = slow.next
		return slow