Challenge: The Middle Node

Lab Python Beginner 10 points

Build a linked list from the input and print the value of the middle node using slow and fast pointers. If there are two middle nodes, print the second one.

Input

One line of values.

Output

The middle value.

Example

Input

1 2 3 4 5

Output

Sample input available Sample output available

Editor

Python

Hints

slow moves 1 step, fast moves 2 steps.

Stop when fast is None or fast.next is None.

Solution explanation

One pass, no counting first: when fast hits the end, slow is in the middle.

Show solution

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


values = input().split()
head = None
for v in reversed(values):
    node = Node(v)
    node.next = head
    head = node
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
print(slow.value)

Output

Answer