单链表

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 *head = nullptr;
    Node *tail = nullptr;

    for(int i = 0; i < n; i ++)
    {
        Node *node  = new Node(arr[i]);

        if(head == nullptr)
        {
            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;
}

//按位查找
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;
}

//删除下标为index的节点
//需要先找到index - 1的节点，在删除index节点
void deleteNode(Node *head, int index)
{
    Node *p = head;
    for(int i = 0; i < index - 1; i ++)
        p = p -> next;
    p -> next = p -> next -> next;
}

//遍历链表
void print(Node *head)
{
    for(Node *p = head; p; p = p -> next)
        cout << p - val << " ";
    cout << endl;
}

int main()
{
    int a[] = {1, 2, 3, 4};
    int n = sizeof(a)/ sizeof(int);

    Node *head = CreateListByTail(a,n);
    print(head);

    insertNode(head, 2, 0);
    print(head);

    deleteNode(head, 2);
    print(head);

    return 0;
}