#include <iostream>

using namespace std;

// 节点定义
struct Node {
    int val;
    Node *next;

    Node(int x) : val(x), next(NULL) {}
};


Node *CreateListByHead(int arr[], int n) {
    Node *head = NULL;

        for (int i = 0; i < n; i++) {
        Node *node = new Node(arr[i]);
        if(head==NULL)
        {
            head=node;
        }else
        {
            node->next = head;
            head = node;
        }
        }
            return head;
}
Node *CreateListWithHead(int arr[], int n) {
    Node*dummy=new Node(-1);
    for(int i=0;i<n;i++)
    {
        Node*node=new Node(arr[i]);
        node->next=dummy->next;
        dummy->next=node;
    }
    return dummy->next;
}
Node *CreateListByTail(int arr[], int n) {
    Node*tail=NULL;
    Node*head=NULL;

    for(int i=0;i<n;i++)
    {
        Node*node=new Node(arr[i]);
        if(tail==NULL)
        {
         head=node;
         tail=node;
        }else
        {
            tail->next=node;
            tail=node;
        }
    }
    return head;
}
Node *CreateListWithTail(int arr[], int n) {
    Node*dummy=new Node(-1);
    Node*tail=dummy;
    for(int i=0;i<n;i++)
    {
        Node*node=new Node(arr[i]);
        tail->next=node;
        tail=node;
    }
    return dummy->next;
}
//下标从0开始
Node *getNodeByIndex(Node *head, int i)
{
    Node*p=head;
    while(i--)
    {
        p=p->next;
    }
    return p;
}
Node *getNodeByValue(Node *head, int e)
{
    for(Node*p=head;p;p=p->next)
    {
        if(p->val==e)
        {
            return p;
        }
    }
    return NULL;
}
Node* insertNode(Node* head, int index, int x)
{
    Node*dummy=new Node(-1);
    dummy->next=head;
    Node*cur=dummy;
    for(int i=0;i<index;i++)
    {
        cur=cur->next;
    }
    Node*newnode=new Node(x);
    newnode->next=cur->next;
    cur->next=newnode;
    head=dummy->next;
    return head;
}
Node* deleteNode(Node* head, int index)
{
    Node*dummy=new Node(-1);
    dummy->next=head;
    Node *p = dummy;
    for (int i = 0; i < index; i ++)
        p = p->next;
    p->next = p->next->next;
    head=dummy->next;
    return head;
}
void print(Node *head)
{
    for (Node *p = head; p; p = p->next)
        cout << p->val << ' ';
    cout << endl;
} 


int main() 
{
    int a[] = {1, 5, 6, 2, 9, 2};
    int n = sizeof(a) / sizeof(int);
    Node *head =CreateListWithTail(a, n);
    head=insertNode(head,0,3);
    print(head);

    return 0;
}