Given a non-empty, singly linked list with head node head, return a middle node of linked list.
If there are two middle nodes, return the second middle node.
Example 1:
Input: [1,2,3,4,5] Output: Node 3 from this list (Serialization: [3,4,5]) The returned node has value 3. (The judge's serialization of this node is [3,4,5]). Note that we returned a ListNode object ans, such that: ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.
Example 2:
Input: [1,2,3,4,5,6] Output: Node 4 from this list (Serialization: [4,5,6]) Since the list has two middle nodes with values 3 and 4, we return the second one.
Description taken from https://leetcode.com/problems/middle-of-the-linked-list/.
#O(N) Time, O(1) Spaceclass Solution: def middleNode(self, head: ListNode) -> ListNode: slow = fast = head while fast is not None and fast.next is not None: slow = slow.next fast = fast.next.next return slowAn intuitive approach would be to traverse the linked list and add each node to an array that you would retrieve the middle element from. Another approach that would be optimal on paper since it would also be linear time, would be to traverse the linked list and save an integer count of the number of nodes, then traverse one more and return once the iterator has reached the median value.
How we would do this in one pass, however, is to use Floyd's Tortoise and Hare algorithm.
If we have one pointer going twice as fast as another, then by the time the fast pointer reaches the end of the list, the slow pointer going half as fast will be halfway there.
We will initialize the slow and fast pointers at the head of the linked list.
Here we can picture the tortoise and hare standing at the starting line.
slow = fast = head
The gun fires and both the tortoise and hare begin the race.
While the hare hasn't reached the finish line, and while his next step isn't past the finish line, the race is still going.
while fast is not None and fast.next is not None:
While the race is still going, we'll let the tortoise and the hare continue to run. The hare's steps are twice as long as the hare's, so we'll increment accordingly.
slow = slow.next fast = fast.next.next
When the hare touches or passes the finish line, the slowpoke tortoise will be halfway done with the track. That is perfect because we're looking for the halfway mark!
We'll return where the tortoise is.
return slow
Floyd's Algorithm is very handy, let's make sure we have it added to our toolbelts.