No code for Go?
We added boilerplate for Go!
Just for fun, to return first middle we check 1 more node ahead.
In Python, while condition becomes while fast and fast.next and fast.next.next:.
The parameter passed in for the function middleOfLinkedList(nodes) is misleading. It is plural “nodes”, implying it’s a list or an array. You should change it to “head”, as it’s the first node in the linked list.
Thanks, we’ve fixed it.
why time complexity would be O(n/2) if we are traversing through the end of the linkedlist?
because we don’t go through every node but only traverse by 2 using the “fast”.
The solution seems a bit misleading given the input parameters. The solution implies each value equals the position of the linked list, but the question doesn’t exactly say anything about what each value is.
I have a question. Why the proposed solution is better than traversing the list once to get length L, and then traversing L/2 to find the middle node? It seems to me that in terms of big O analysis the number of operations will be exactly the same, since each movement of the faster pointer has to follow a pointer twice anyway. So we get L / 2 pointer operations from the slow pointer, but still L operations from the fast pointer. The only difference I can see is potentially in the cache locality if the list is long.
You can walk through the linked list without keeping pointers, or going through the list in two different places:
def middle_of_linked_list(head: Node) -> int:
node = head
mid = head.val
while node:
# Move middle value every two hops
if node.next and node.next.next:
mid = node.val
node = node.next
return mid
very nice ! the solution blow my mind