The same fast and slow pointer trick finds the middle of a list in a single pass. When the fast pointer reaches the end, the slow pointer sits at the middle.
Implement middle(head) that returns the value stored at the middle node. For a list of even length there are two middles, so return the value of the second one. You may assume the list is non-empty and has no cycle.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def from_list(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def to_list(head):
out = []
node = head
while node is not None:
out.append(node.value)
node = node.next
return out
def reverse(head):
prev = None
cur = head
while cur is not None:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev
def has_cycle(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
def middle(head):
"""Return the value at the middle node (the second middle if even length)."""
# TODO: advance slow by one and fast by two until fast runs out
pass
The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
The same fast and slow pointer trick finds the middle of a list in a single pass. When the fast pointer reaches the end, the slow pointer sits at the middle.
Implement middle(head) that returns the value stored at the middle node. For a list of even length there are two middles, so return the value of the second one. You may assume the list is non-empty and has no cycle.
Press Run Tests or ⌘↩ to check your solution.