Middle of the LinkedList Ecrivez une méthode qui renvoie un nœud intermédiaire dans une LinkedList, en spécifiant le début d'une seule liste liée. Si le nombre total de nœuds dans LinkedList est pair, renvoie le deuxième nœud intermédiaire.
Input: 1 -> 2 -> 3 -> 4 -> 5 -> null Output: 3
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null Output: 4
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null Output: 4
Solution L'une des stratégies de force brute consiste à compter d'abord le nombre de nœuds dans la LinkedList, puis à trouver le nœud central dans la deuxième itération. Il est important de pouvoir le faire en une seule itération.
Utilisez les méthodes de pointeur rapide et lent pour vous assurer que le pointeur rapide est toujours deux fois le nœud devant le pointeur lent. Ainsi, lorsque le pointeur rapide atteint la fin de la LinkedList, le pointeur lent pointe vers le nœud central.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def find_middle_of_linked_list(head):
# Time Complexity O(N)
# Space Complexity O(1)
slow = head
fast = head
while (fast is not None and fast.next is not None):
slow = slow.next
fast = fast.next.next
return slow
def main():
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
print("Middle Node: " + str(find_middle_of_linked_list(head).value))
head.next.next.next.next.next = Node(6)
print("Middle Node: " + str(find_middle_of_linked_list(head).value))
head.next.next.next.next.next.next = Node(7)
print("Middle Node: " + str(find_middle_of_linked_list(head).value))
main()
Recommended Posts