单链表的插入和删除

单链表是一种常见的数据结构，它由节点组成，每个节点包含数据和一个指向下一个节点的指针。单链表的插入和删除操作是常见的操作，下面是它们的具体实现。

单链表的插入操作分为三种情况：

1. 在头部插入节点

当需要在单链表的头部插入一个节点时，只需将新节点的指针指向原头节点，然后将头指针指向新节点即可。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* insertAtHead(ListNode* head, int val) {
    ListNode* newHead = new ListNode(val);
    newHead->next = head;
    return newHead;
}

2. 在尾部插入节点

当需要在单链表的尾部插入一个节点时，需要先找到最后一个节点，然后将最后一个节点的指针指向新节点即可。

ListNode* insertAtTail(ListNode* head, int val) {
    ListNode* newTail = new ListNode(val);
    if (head == nullptr) {
        return newTail;
    }
    ListNode* cur = head;
    while (cur->next != nullptr) {
        cur = cur->next;
    }
    cur->next = newTail;
    return head;
}

3. 在中间插入节点

当需要在单链表的中间插入一个节点时，需要先找到插入位置的前一个节点，然后将前一个节点的指针指向新节点，新节点的指针指向插入位置的节点即可。

ListNode* insertInMiddle(ListNode* head, int val, int pos) {
    ListNode* newNode = new ListNode(val);
    if (head == nullptr || pos == 1) {
        newNode->next = head;
        return newNode;
    }
    ListNode* cur = head;
    int cnt = 1;
    while (cur != nullptr && cnt < pos - 1) {
        cur = cur->next;
        cnt++;
    }
    if (cur == nullptr) {
        return head;
    }
    newNode->next = cur->next;
    cur->next = newNode;
    return head;
}

单链表的删除操作也分为三种情况：

1. 删除头节点

当需要删除单链表的头节点时，只需将头指针指向头节点的下一个节点即可。

ListNode* deleteAtHead(ListNode* head) {
    if (head == nullptr) {
        return nullptr;
    }
    ListNode* newHead = head->next;
    delete head;
    return newHead;
}

2. 删除尾节点

当需要删除单链表的尾节点时，需要先找到倒数第二个节点，将它的指针指向空即可。

ListNode* deleteAtTail(ListNode* head) {
    if (head == nullptr) {
        return nullptr;
    }
    if (head->next == nullptr) {
        delete head;
        return nullptr;
    }
    ListNode* cur = head;
    while (cur->next->next != nullptr) {
        cur = cur->next;
    }
    delete cur->next;
    cur->next = nullptr;
    return head;
}

3. 删除中间节点

当需要删除单链表的中间节点时，需要先找到要删除节点的前一个节点，将它的指针指向要删除节点的下一个节点即可。

ListNode* deleteInMiddle(ListNode* head, int pos) {
    if (head == nullptr) {
        return nullptr;
    }
    if (pos == 1) {
        ListNode* newHead = head->next;
        delete head;
        return newHead;
    }
    ListNode* cur = head;
    int cnt = 1;
    while (cur != nullptr && cnt < pos - 1) {
        cur = cur->next;
        cnt++;
    }
    if (cur == nullptr || cur->next == nullptr) {
        return head;
    }
    ListNode* toDelete = cur->next;
    cur->next = cur->next->next;
    delete toDelete;
    return head;
}