#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;
}
void displayList(struct node* head){
    struct node* current = head;
        while(current!=NULL){
                printf("%d ", current -> data);
                current = current->next;
    }
    printf("\n");
}
/*
 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
}

/*
 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->next;
            current->next = newNode;
            return;
        }
        count++;
        current = current->next;
    }
}

int main (){
     struct node* myList = BuildOneTwoThree(); // build {1, 2, 3}
     displayList(myList);
     //{1, 2, 3}
     InsertNth(&myList, 0, 13);
     displayList(myList);
     //{13, 1, 2, 3}
     InsertNth(&myList, 1, 5);
     displayList(myList);
     //{13, 5, 1, 2, 3}
     InsertNth(&myList, 6, 20);
     displayList(myList);
     //{13, 5, 1, 2, 3, 20}
     displayList(myList);
     return 0;
}