Middle of the LinkedList Schreiben Sie eine Methode, die einen Zwischenknoten in eine LinkedList zurückgibt, und geben Sie den Anfang einer einzelnen verknüpften Liste an. Wenn die Gesamtzahl der Knoten in der LinkedList gerade ist, wird der zweite Zwischenknoten zurückgegeben.
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 Eine der Brute-Force-Strategien besteht darin, zuerst die Anzahl der Knoten in der LinkedList zu zählen und dann den zentralen Knoten in der zweiten Iteration zu finden. Es ist wichtig, dies in einer einzigen Iteration tun zu können.
Verwenden Sie die Methoden für schnelle und langsame Zeiger, um sicherzustellen, dass der schnelle Zeiger immer doppelt so groß ist wie der Knoten vor dem langsamen Zeiger. Wenn der schnelle Zeiger das Ende der LinkedList erreicht, zeigt der langsame Zeiger auf den zentralen Knoten.
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