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

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

struct node* BuildOneTwoThree() {
    struct node* head = NULL;
    struct node* second = NULL;
    struct node* third = NULL;
    head = (struct node*) malloc(sizeof(struct node)); // allocate 3 nodes in the heap
    second = (struct node*) malloc(sizeof(struct node));
    third = (struct node*) malloc(sizeof(struct node));
    head->data = 1; // setup first node
    head->next = second; // note: pointer assignment rule
    second->data = 2; // setup second node
    second->next = third;
    third->data = 3; // setup third link
    third->next = NULL;
    // At this point, the linked list referenced by "head"
    // matches the list in the drawing.
    return head;
}

/*
 Takes a list and a data value.
 Creates a new link with the given data and pushes
 it onto the front of the list.
 The list is not passed in by its head pointer.
 Instead the list is passed in as a "reference" pointer
 to the head pointer -- this allows us
 to modify the caller's memory.
*/
void Push(struct node** headRef, int data) {
    struct node* newNode = (struct node*) malloc(sizeof(struct node));
    newNode->data = data;
    newNode->next = *headRef; // The '*' to dereferences back to the real head
    *headRef = newNode; // ditto
}
void PushTest() {
    struct node* head = BuildOneTwoThree();// suppose this returns the list {2, 3}
    Push(&head, 1); // note the &
    Push(&head, 13);
    // head is now the list {13, 1, 2, 3}
}

// Return the number of nodes in a list (while-loop version)
int Length(struct node* head) {
    int count = 0;
    struct node* current = head;
    while (current != NULL) {
    count++;
    current = current->next;
    }
    return(count);
}

void displayList(struct node* head){
    for(struct node* current = head;current!=NULL;current = current->next)
        printf("%d ", current -> data);
    printf("\n");
}

//#1
/*
 Given a list and an int, return the number of times that int occurs
 in the list.
*/
int Count(struct node* head, int searchFor) {
    int count = 0;
    struct node *current;
    for(current = head;current !=NULL;current = current->next){
        if (current->data == searchFor)
            count++;
    }
    return count;
}

int CountTest() {
    struct node* myList = BuildOneTwoThree(); // build {1, 2, 3}
    return Count(myList, 2); // returns 1 since there's 1 '2' in the list
}

//#2
// Given a list and an index, return the data
// in the nth node of the list. The nodes are numbered from 0.
// Assert fails if the index is invalid (outside 0..lengh-1).
int GetNth(struct node* head, int index) {
    int count = 0;
    struct node* current;
    for(current =head;current!=NULL;current=current->next){
        if (count == index)
            return current->data;
        count++;
    }
    return -1;
}

//#3
void DeleteList(struct node** headRef) {
    struct node* current = *headRef;
    struct node* temp;
    while(current!=NULL){
        temp= current;
        current = current->next;
        free(temp);
    }
    *headRef = NULL;
}

void DeleteListTest() {
    struct node* myList = BuildOneTwoThree(); // build {1, 2, 3}
    DeleteList(&myList); // deletes the three nodes and sets myList to NULL
}

//#4
/*
 The opposite of Push(). Takes a non-empty list
 and removes the front node, and returns the data
 which was in that node.
*/
int Pop(struct node** headRef) {
    if (*headRef==NULL)
        return -1;
    struct node* current = *headRef;
    int result = current->data;
    *headRef = (*headRef)->next;
    free(current);
    return result;
}

void PopTest() {
    struct node* head = BuildOneTwoThree(); // build {1, 2, 3}
    int a = Pop(&head); // deletes "1" node and returns 1
    int b = Pop(&head); // deletes "2" node and returns 2
    int c = Pop(&head); // deletes "3" node and returns 3
    int len = Length(head); // the list is now empty, so len == 0
}



//#5
/*
 A more general version of Push().
 Given a list, an index 'n' in the range 0..length,
 and a data element, add a new node to the list so
 that it has the given index.
*/
void InsertNth(struct node** headRef, int index, int data) {
    if(index==0){
        Push(headRef, data);
        return;
    }
    struct node* current = *headRef;

    struct node* newNode;
    newNode = (struct node*) malloc(sizeof(struct node));
    newNode->data = data;
    int count =0;

    while(current!=NULL){
        if (count==index-1){
            newNode->next = current->next;
            current->next = newNode;
            return;
        }
        count++;
        current = current->next;
    }
}


void InsertNthTest() {
    struct node* head = NULL; // start with the empty list
    InsertNth(&head, 0, 13); // build {13)
    InsertNth(&head, 1, 42); // build {13, 42}
    InsertNth(&head, 1, 5); // build {13, 5, 42}
    displayList(head);
    DeleteList(&head); // clean up after ourselves
}



//#6
void SortedInsert(struct node** headRef, struct node* newNode) {
    if (*headRef == NULL || (*headRef)->data >= newNode -> data){
        newNode->next = *headRef;
        *headRef = newNode;
        return;
    }
    struct node* current = *headRef;
    //struct node* temp;
    while(current->next!=NULL){
        if (current->data <= newNode->data && current->next->data >= newNode->data){
            newNode->next = current->next;
            current->next = newNode;
            return;
        }
        current = current->next;
    }
    current->next = newNode;
    newNode->next=NULL;
}

//#7

// Given a list, change it to be in sorted order (using SortedInsert()).
void Sort(struct node** headRef) {
    struct node* result = NULL;
    struct node* current = *headRef;
    struct node* temp;

    while(current!=NULL){
        temp = current->next;
        SortedInsert(&result, current);
        current = temp;
    }

    *headRef = result;
}

//#8
// Append 'b' onto the end of 'a', and then set 'b' to NULL.
void Append(struct node** aRef, struct node** bRef) {
    if (*aRef==NULL){
        *aRef= *bRef;
        *bRef = NULL;
        return;
    }

    struct node* current = *aRef;

    while(current->next!= NULL){
        current = current->next;
    }

    current->next = *bRef;
    *bRef=NULL;
}


//#9
/*
 Split the nodes of the given list into front and back halves,
 and return the two lists using the reference parameters.
 If the length is odd, the extra node should go in the front list.
*/
void FrontBackSplit(struct node* source, struct node** frontRef, struct node** backRef) {
    struct node* current;
    int length = 0;

    for(current = source;current!=NULL;current=current->next)
        length++;
    if (length<2){
        *frontRef = source;
        *backRef = NULL;
    }
    else {
        length = (length-1)/2;
        current = source;

        for(int i =0;i<length;i++){
            current = current->next;
        }
        *frontRef = source;
        *backRef= current->next;
        current->next = NULL;
    }
}


//#10

/*
 Remove duplicates from a sorted list.
*/
void RemoveDuplicates(struct node* head) {
    if (head == NULL)
        return;
    struct node* current = head;
    struct node* temp;
    while(current->next!=NULL){
        if(current->data == current->next->data){
            temp = current->next;
            current->next = current->next->next;
            free(temp);
        }
        else{
            current = current->next;
        }
    }
}

//#11
/*
 Take the node from the front of the source, and move it to
 the front of the dest.
 It is an error to call this with the source list empty.
*/
void MoveNode(struct node** destRef, struct node** sourceRef) {
    if(sourceRef == NULL)
        return;
    struct node* current = *sourceRef;
    *sourceRef = (*sourceRef)->next;
    current->next = *destRef;
    *destRef = current;
}

void MoveNodeTest() {
    struct node* a = BuildOneTwoThree(); // the list {1, 2, 3}
    struct node* b = BuildOneTwoThree();
    displayList(a);
    displayList(b);
    printf("\nnow\n");
    MoveNode(&a, &b);
    displayList(a);
    displayList(b);
    // a == {1, 1, 2, 3}
    // b == {2, 3}
}

//#12
/*
 Given the source list, split its nodes into two shorter lists.
 If we number the elements 0, 1, 2, ... then all the even elements
 should go in the first list, and all the odd elements in the second.
 The elements in the new lists may be in any order.
*/
void AlternatingSplit(struct node* source, struct node** aRef, struct node** bRef) {
    if(source==NULL)
        return;

    struct node* temp1;
    temp1 = (struct node*) malloc(sizeof(struct node));

    struct node* temp2;
    temp2 = (struct node*) malloc(sizeof(struct node));

    struct node* current = source;

    int count1 = 0;
    int count2 = 0;

    for(int i = 0; i<Length(source);i++){
        if (i%2==0&&count1==0){
            *aRef = current;
            count1++;
            temp1 = *aRef;
        }
        else if (i%2==0){
            temp1->next = current;
            temp1 = temp1->next;
        }
        else if (i%2!=0&&count2==0){
            *bRef = current;
            count2++;
            temp2 = *bRef;
        }
        else if (i%2!=0){
            temp2->next = current;
            temp2=temp2->next;
        }
        current = current->next;
    }
}

/*void AlternatingSplit(struct node* source, struct node** aRef, struct node** bRef){
    struct node* a = NULL; // Split the nodes to these 'a' and 'b' lists
    struct node* b = NULL;

    struct node* current = source;
    while(current!=NULL){
        MoveNode(&a, &current);
        if (current!=NULL)
            MoveNode(&b, &current);
    }
    *aRef = a;
    *bRef = b;
}*/


int main (){
    //#2
    struct node* myList = BuildOneTwoThree(); // build {1, 2, 3}
    DeleteList(&myList);
    InsertNth(&myList, 0, 1);
    InsertNth(&myList, 1, 2);
    InsertNth(&myList, 2, 1);
    InsertNth(&myList, 3, 2);
    InsertNth(&myList, 4, 1);
    InsertNth(&myList, 5, 2);

    struct node* evenList;
    struct node* oddList;

    evenList = (struct node*) malloc (sizeof(struct node));
    oddList = (struct node*) malloc (sizeof(struct node));

    evenList = NULL;
    oddList = NULL;

    displayList(evenList);
    displayList(oddList);
    displayList(myList);

    AlternatingSplit(myList, &evenList, &oddList);

    displayList(evenList);
    displayList(oddList);
    displayList(myList);

    return 0;
}