// Arup Guha
// 12/5/2023
// Solutions to 2023 COP 3502 Final Exam Part B Question 2 - Both Versions

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

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

node* insert(node* front, int val) ;
node* oddrankedterms(node* front);
void freelist(node* front);
void print(node* front);
node* newrevlist(node* front);

int main() {

    node* list = NULL;

    // Make a simple list and print.
    int vals[6] = {2, 6, 5, 7, 3, 9};
    for (int i=5; i>=0; i--)
        list = insert(list, vals[i]);
    print(list);

    // Test odd ranked terms...
    node* newlist = oddrankedterms(list);
    print(newlist);

    // Add item and retest.
    list = insert(list, 13);
    node* newnewlist = oddrankedterms(list);
    print(newnewlist);

    // Test reverse too...
    node* revme = newrevlist(list);
    print(list);
    print(revme);

    // Free my lists.
    freelist(revme);
    freelist(list);
    freelist(newlist);
    freelist(newnewlist);

    return 0;
}

// Print list pointed to by front, for testing.
void print(node* front) {
    while (front != NULL) {
        printf("%d ", front->data);
        front = front->next;
    }
    printf("\n");
}

// Free memory for all dynamically allocated nodes in list pointed to by front.
void freelist(node* front) {
    if (front == NULL) return;
    freelist(front->next);
    free(front);
}

// Creates a new list with the 1st, 3rd, 5th, etc. items in the list pointed to by front.
node* oddrankedterms(node* front) {

    // This is easy and necessary.
    if (front == NULL) return NULL;

    // If we get here, list is at least size one.
    node* tmp = malloc(sizeof(node));
    tmp->data = front->data;
    tmp->next = NULL;

    // This if is key. Only recursively call if necessary. Avoids NULL ptr error.
    if (front->next != NULL)
        tmp->next = oddrankedterms(front->next->next);

    // Front of the new list.
    return tmp;
}

// Inserts a node storing val to the front of the list pointed to by front, returning a pointer to
// the new front.
node* insert(node* front, int val) {
    node* tmp = malloc(sizeof(node));
    tmp->data = val;
    tmp->next = front;
    return tmp;
}

// Returns a new list storing the items in the list pointed to by front in reverse order.
node* newrevlist(node* front) {

    // New list will be here.
    node* cur = NULL;

    // Go through input list.
    while (front != NULL) {

        // Make this node.
        node* tmp = malloc(sizeof(node));
        tmp->data = front->data;

        // Insert to front of list cur.
        tmp->next = cur;

        // Update cur.
        cur = tmp;

        // Go to next in the list.
        front = front->next;
    }

    // Ta da!
    return cur;
}