单链表实现在第i个结点前插入值为x的结点

单链表插入操作可以分为两种情况：

第一种情况，插入到链表的头部：

#include <iostream>
using namespace std;

// 链表节点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 插入节点到链表的头部
ListNode* insertNodeAtHead(ListNode* head, int val) {
    ListNode* newNode = new ListNode(val);
    newNode->next = head;
    return newNode;
}

int main() {
    ListNode* head = NULL;
    head = insertNodeAtHead(head, 3);
    head = insertNodeAtHead(head, 2);
    head = insertNodeAtHead(head, 1);

    // 输出链表
    ListNode* p = head;
    while (p != NULL) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;

    return 0;
}

第二种情况，插入到链表的中间或尾部：

#include <iostream>
using namespace std;

// 链表节点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 单链表在第i个节点前插入值为x的节点
ListNode* insertNode(ListNode* head, int val, int pos) {
    ListNode* newNode = new ListNode(val);

    if (pos == 1) {
        newNode->next = head;
        return newNode;
    }

    ListNode* p = head;
    int i = 1;
    while (p != NULL && i < pos - 1) {
        p = p->next;
        i++;
    }

    if (p == NULL) {
        return head;
    }

    newNode->next = p->next;
    p->next = newNode;

    return head;
}

int main() {
    ListNode* head = NULL;
    head = insertNode(head, 1, 1);
    head = insertNode(head, 3, 2);
    head = insertNode(head, 2, 2);
    head = insertNode(head, 5, 4);
    head = insertNode(head, 4, 4);

    // 输出链表
    ListNode* p = head;
    while (p != NULL) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;

    return 0;
}