#include <stdio.h>
#include <stdlib.h>

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

struct node *newNode(int val) {
    struct node *n = malloc(sizeof(struct node));
    n->data = val;
    n->next = NULL;
    return n;
}

void append(struct node **head, int val) {
    struct node *n = newNode(val);

    if (*head == NULL) {
        *head = n;
        return;
    }

    struct node *curr = *head;
    while (curr->next != NULL) {
        curr = curr->next;
    }
    curr->next = n;
}

int medianLinkedList(struct node *head) {
    //TODO
}

int main(void) {

    // -------------------------
    // Test 1: Single element
    // -------------------------
    struct node *t1 = NULL;
    append(&t1, 5);

    printf("Test 1: %d\n", medianLinkedList(t1));
    // Expected: 5


    // -------------------------
    // Test 2: Odd number
    // 1 -> 3 -> 5
    // -------------------------
    struct node *t2 = NULL;
    append(&t2, 1);
    append(&t2, 3);
    append(&t2, 5);

    printf("Test 2: %d\n", medianLinkedList(t2));
    // Expected: 3


    // -------------------------
    // Test 3: Even number
    // 1 -> 2 -> 3 -> 4
    // -------------------------
    struct node *t3 = NULL;
    append(&t3, 1);
    append(&t3, 2);
    append(&t3, 3);
    append(&t3, 4);

    printf("Test 3: %d\n", medianLinkedList(t3));
    // Expected: depends on spec (2 or 3)


    // -------------------------
    // Test 4: Larger odd list
    // 2 -> 4 -> 6 -> 8 -> 10
    // -------------------------
    struct node *t4 = NULL;
    append(&t4, 2);
    append(&t4, 4);
    append(&t4, 6);
    append(&t4, 8);
    append(&t4, 10);

    printf("Test 4: %d\n", medianLinkedList(t4));
    // Expected: 6


    // -------------------------
    // Test 5: Even longer list
    // 10 -> 20 -> 30 -> 40 -> 50 -> 60
    // -------------------------
    struct node *t5 = NULL;
    append(&t5, 10);
    append(&t5, 20);
    append(&t5, 30);
    append(&t5, 40);
    append(&t5, 50);
    append(&t5, 60);

    printf("Test 5: %d\n", medianLinkedList(t5));
    // Expected: 30 or 40


    // -------------------------
    // Test 6: Negative values
    // -10 -> -5 -> 0 -> 5 -> 10
    // -------------------------
    struct node *t6 = NULL;
    append(&t6, -10);
    append(&t6, -5);
    append(&t6, 0);
    append(&t6, 5);
    append(&t6, 10);

    printf("Test 6: %d\n", medianLinkedList(t6));
    // Expected: 0
    return 0;
}