Problem

Given a singly linked list, write a function that returns the middle node of the list. If the list has an even number of nodes, the function should return the node at the start of the second half of the list.
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6
Output: 4

Solution

#include <iostream>
#include <vector>

using namespace std;

struct Node {
    int data;
    Node* next;
};

Node* createNode(int data) {
    Node* node = new Node;
    node->data = data;
    node->next = NULL;
    return node;
}

Node* createList(vector<int> data) {
    Node* head = createNode(data[0]);
    Node* current = head;
    for (int i = 1; i < data.size(); i++) {
        current->next = createNode(data[i]);
        current = current->next;
    }
    return head;
}

void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

Node* getMiddleNode(Node* head) {
    Node* slow = head;
    Node* fast = head; while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

int main() {
    vector<int> data = {1, 2, 3, 4, 5, 6};
    Node* head = createList(data);
    printList(head);
    Node* middle = getMiddleNode(head);
    cout << middle->data << endl;
    return 0;
}