// Arup Guha
// 10/11/2023
// Solution to COP 3502 Section 4 Exam 1 Part A Question 3

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

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

void freeList(node* list);
node* addFront(node* list, int val);
node* reverse(node* list);
node* reverse_alt(node* list);

void print(node* list);

int main() {

    // Add some nodes and print.
    node* mine = NULL;
    mine = addFront(mine, 3);
    mine = addFront(mine, 12);
    mine = addFront(mine, 7);
    mine = addFront(mine, 1);
    mine = addFront(mine, 8);
    mine = addFront(mine, 4);
    print(mine);
    printf("\n");

    // Call reverse and reprint.
    mine = reverse(mine);
    print(mine);
    freeList(mine);
    return 0;
}

// Frees the memory in the nodes pointed to by the linked list pointer list.
void freeList(node* list) {
    if (list == NULL) return;
    freeList(list->next);
    free(list);
}

// Prints all the items in the linked list pointed to by liist.
void print(node* list) {
    if (list == NULL) return;
    printf("%d ", list->data);
    print(list->next);
}

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

// Reverses the linked list pointed to by list and returns a pointer to the new front of the list.
node* reverse(node* list) {

    // These two don't have any changes when reversed.
    if (list == NULL || list->next == NULL) return list;

    // Reverse the rest of the list.
    node* rest = reverse(list->next);

    // Iterate through the already reversed rest of the list.
    node* tmp = rest;
    while (tmp->next != NULL) tmp = tmp->next;

    // Link last item in reversed list to the first item in the original list.
    tmp->next = list;

    // Set this one's pointer to NULL since it's now the last in the list.
    list->next = NULL;

    // This is a pointer to the new front of the list.
    return rest;
}

/*** This is just added for fun. It's O(n) instead of O(n^2) ***/
node* reverse_alt(node* list) {

    // These two don't have any changes when reversed.
    if (list == NULL || list->next == NULL) return list;

    // Save this.
    node* secondNode = list->next;

    // Reverse the rest of the list.
    node* rest = reverse(list->next);

    // Link last item in reversed list to the first item in the original list.
    secondNode->next = list;

    // Set this one's pointer to NULL since it's now the last in the list.
    list->next = NULL;

    // This is a pointer to the new front of the list.
    return rest;
}