双链表的插入

双向链表（Doubly Linked List）是一种链式数据结构，每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点。插入操作可以分为三种情况：

1. 在头部插入节点
2. 在尾部插入节点
3. 在中间插入节点

下面是 C++ 实现双向链表的插入操作：

#include <iostream>

using namespace std;

// 双向链表节点
struct ListNode {
    int val;
    ListNode* prev; // 前驱节点指针
    ListNode* next; // 后继节点指针
    ListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};

void insertAtHead(ListNode** head, int val) {
    ListNode* newNode = new ListNode(val);
    newNode->next = *head;
    if (*head) {
        (*head)->prev = newNode;
    }
    *head = newNode;
}

void insertAtTail(ListNode** head, int val) {
    ListNode* newNode = new ListNode(val);
    if (*head == nullptr) {
        *head = newNode;
        return;
    }
    ListNode* curNode = *head;
    while (curNode->next) {
        curNode = curNode->next;
    }
    curNode->next = newNode;
    newNode->prev = curNode;
}

void insertAtPos(ListNode** head, int pos, int val) {
    if (pos < 1) {
        return;
    }
    if (pos == 1) {
        insertAtHead(head, val);
        return;
    }
    ListNode* newNode = new ListNode(val);
    ListNode* curNode = *head;
    for (int i = 1; i < pos - 1 && curNode; i++) {
        curNode = curNode->next;
    }
    if (curNode == nullptr) {
        return;
    }
    newNode->prev = curNode;
    newNode->next = curNode->next;
    if (curNode->next) {
        curNode->next->prev = newNode;
    }
    curNode->next = newNode;
}

void printList(ListNode* head) {
    ListNode* curNode = head;
    while (curNode) {
        cout << curNode->val << " ";
        curNode = curNode->next;
    }
    cout << endl;
}

int main() {
    ListNode* head = nullptr;
    insertAtHead(&head, 1);
    insertAtHead(&head, 2);
    insertAtTail(&head, 3);
    insertAtPos(&head, 2, 4);
    printList(head);
    return 0;
}

在上述代码中，`insertAtHead` 函数在头部插入节点，`insertAtTail` 函数在尾部插入节点，`insertAtPos` 函数在指定位置插入节点。需要注意的是，在使用 `insertAtHead` 函数和 `insertAtPos` 函数时，需要传入头节点指针的指针，以便在函数中修改头节点。