Challenge: The Middle Coach

Lab Java Beginner 10 points

Build a linked list of n numbers and print the value of the middle node using slow and fast pointers (don't count the length first). With an even length, print the second of the two middle nodes.

Input

Line 1: n (n ≥ 1). Line 2: n whole numbers.

Output

The middle value.

Example

Input

5
1 2 3 4 5

Output

Sample input available Sample output available

Editor

Java

Hints

slow moves 1 step, fast moves 2.

Stop when fast is null or fast.next is null.

Solution explanation

The fast pointer covers the list twice as quickly, so slow is in the middle when fast finishes: one pass, O(n).

Show solution

import java.util.Scanner;

class Node {
    int value;
    Node next;
    Node(int value) { this.value = value; }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node head = null, tail = null;
        for (int i = 0; i < n; i++) {
            Node node = new Node(sc.nextInt());
            if (head == null) head = tail = node;
            else { tail.next = node; tail = node; }
        }
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        System.out.println(slow.value);
    }
}

Output

Answer