Challenge: The Middle Node

Lab C++ Beginner 10 points

Build a linked list and print the middle value using slow and fast pointers. With two middles, print the second.

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

C++

Hints

slow moves 1 step, fast moves 2.

Stop when fast or fast->next is nullptr.

Solution explanation

One pass and no counting: when fast reaches the end, slow is in the middle.

Show solution

#include <iostream>
using namespace std;

struct Node {
    int value;
    Node* next;
    Node(int v) : value(v), next(nullptr) {}
};

int main() {
    int n;
    cin >> n;
    Node* head = nullptr;
    Node* tail = nullptr;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        Node* node = new Node(x);
        if (!head) head = tail = node;
        else { tail->next = node; tail = node; }
    }
    Node* slow = head;
    Node* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    cout << slow->value << endl;
    return 0;
}

Output

Answer