/////Exercise 1:
// Iterative, call : int sum = sumNodes(head);
int sumNodes(List* head) {
    int sum = 0;
    List* p = head;
    while (p != NULL) {
        sum += p->data;
        p = p->next;
    }

    return sum;
}
// Recursive, call : int sum = 0;  sumNodes(head, &sum);
void sumNodes(List* head, int* sum) {
    if (head != NULL) {
        *sum += head->data;
        sumNodes(head->next, sum);
    }
}


/////Exercise 2:
// Version 1, call : int max = maxList(head);
int maxList(List* head) {
    if (head == NULL) return INT_MIN;
    else{
        int maxRest = maxList( head->next);
        if (head->data > maxRest) maxRest = head->data;
        return maxRest;
    }
}

// Version 2, call : int max = INT_MIN; maxList(head, &max);
void maxList(List* head, int* max) {
    if (head != NULL) {
        if (head->data > *max) *max = head->data;
        maxList(head->next, max);
    }
}

//Exercise 3: call List *p = search(head, elt);
//Iterative
List* search(List *head, int X) {
    List *p = head;

    while (p != NULL) {
        if (current->data == X) {
            return p;
        }
        p = p->next;
    }

    return NULL;
}

//Recursive
List* search(List* head, int X) {
    if (head == NULL) return NULL;
    else if (head->data == X) return head;
    else return search(head->next, X);
}

//Exercise 4
//version 1, call : reverse(head, &headR);
void reverseList(List *head, List **headR){
    if (head != NULL){
        List *next = head->next;
        if (*headR == NULL) {
            *headR = head;
            (*headR)->next = NULL;
        }
        else {
            head->next = *headR;
            *headR = head;
        }

        reverseList(next, headR);
    }
}
//Version 2, call: List *headR = reverseList(head);
List* reverseList(List *head) {

    if (head == NULL || head->next == NULL) return head;
    else {

        List *headR = reverseList(head->next);
        List *previous = head->next;
        previous->next = head;
        head->next = NULL;

        return headR;
    }
}

//Exercise 5, call: insert(&head, X);
void insert(List **head, int X){
    List *newNode = (List*) malloc(sizeof(List));
    newNode->data = X;

    if (*head == NULL || (X < (*head)->data)) {
        newNode->next = *head;
        *head = newNode;

    }
    else {
        List * p = (*head)->next;
        List *prev = *head;
        while(p!=NULL && X > p->data) {
            prev = p;
            p = p->next;
        }
        prev->next = newNode;
        newNode->next = p;
    }
}