Middle of the LinkedList
単一リンクリストの先頭を指定して、LinkedListの中間ノードを返すメソッドを記述します。
LinkedListのノードの総数が偶数の場合は、2番目の中間ノードを返します。
例
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
力ずく戦略の1つは、最初にLinkedListのノード数を数え、次に2番目の反復で中央のノードを見つけることです。 これを1回の反復で実行できるようにするのが肝です。
fastポインターとslowポインターのメソッドを使用して、fastポインターが常にslowポインターよりもノードの2倍先になるようにします。このように、fastポインターがLinkedListの最後に到達すると、slowポインターは中央のノードを指します。
実装
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()