include [HTML_REMOVED]

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 *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++){
if （p->val == e） return p;
}
}

// 在下表为index的位置上插入值为x的新节点
// 先找到index - 1的节点，再在其后插入新节点
void insertNode(Node head, int index, int x){
Node p = head;
for(int i = 0;i < index-1;i++) p = p->next;

Node *node = new Node(x);
node ->next = p->next;
p->next = node;

}

// 删除链表下标为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++){
cout << p ->val <<’ ‘;
cout << endl;
}
}