// Arup Guha
// 10/10/2023
// Code for COP 3502 Exam 1 A Section 1 Question 3

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

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

void mystery(node* list);
node* add(node* front, int item);
void print(node* front);
void freelist(node* list);

int main() {

    // Set up the linked list with the items inserting to create the list in the example.
    node* tmp = NULL;
    int data[8] = {18,19,9,2,13,12,4,8};
    for (int i=0; i<8; i++)
        tmp = add(tmp, data[i]);

    // Print, run mystery and print again.
    print(tmp);
    mystery(tmp);
    printf("\n");
    print(tmp);
    freelist(tmp);

    return 0;
}

// Mystery function for exam, it actually does one pass of bubble sort on the list.
void mystery(node* list) {

    // Nothing if we're length 1 or 2.
    if (list == NULL || list->next == NULL) return;

    // This means that the two terms (first and second) are out of order...
    if (list->data > list->next->data) {

        // This is confusing, but once you go through it, you realize it's a swap!!!
        list->next->data += list->data;
        list->data = list->next->data - list->data;
        list->next->data -= list->data;
    }

    // Recurse on the rest of the list.
    mystery(list->next);
}

// Adds a node storing item to the front of the linked list pointed to by front.
node* add(node* front, int item) {
    node* tmp = malloc(sizeof(node));
    tmp->data = item;
    tmp->next = front;
    return tmp;
}

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

// Free all the nodes in the linked list pointed to by list.
void freelist(node* list) {
    if (list == NULL) return;
    freelist(list->next);
    free(list);
}