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

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

// Insert a new node into a sorted linked list, maintaining
// the sorted order
// 3 7 10 16 (insert 8)..... 3 7 8 10 16
struct node *insert_sorted(struct node *head, int number) {

    // create the new node
    struct node *new_node = malloc(sizeof(struct node));
    new_node->data = number;
    new_node->next = NULL;

    struct node *prev = NULL;
    struct node *curr = head;
    while (curr != NULL && curr->data < number) {
        prev = curr;
        curr = curr->next;
    }

    // edge case: inserting at the head (includes empty list)
    if (prev == NULL) {
        // insert at the head
        new_node->next = head;
        head = new_node;
    } else {
        // insert the new node between prev and curr
        prev->next = new_node;
        // prev->next->next = curr; // this should work
        new_node->next = curr;   // same as above
    }

    return head;
}


// DO NOT CHANGE THE CODE BELOW

struct node *strings_to_list(int len, char *strings[]);
void print_list(struct node *head);


int main(int argc, char *argv[]) {   

    if (argc == 1) {
        printf("Usage %s value list_data\n", argv[0]);
        return 0;
    }
    // create linked list from command line arguments
    int value = atoi(argv[1]);
    struct node *head = strings_to_list(argc - 2, &argv[2]);

    struct node *new_head = insert_sorted(head, value);
    print_list(new_head);

    return 0;
}


// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
    struct node *head = NULL;
    int i = len - 1;
    while (i >= 0) {
        struct node *n = malloc(sizeof (struct node));
        assert(n != NULL);
        n->next = head;
        n->data = atoi(strings[i]);
        head = n;
        i -= 1;
    }   
    return head;
}

// print linked list
void print_list(struct node *head) {
    printf("[");    
    struct node *n = head;
    while (n != NULL) {
        // If you're getting an error here,
        // you have returned an invalid list
        printf("%d", n->data);
        if (n->next != NULL) {
            printf(", ");
        }
        n = n->next;
    }
    printf("]\n");
}