C++ 链表插入操作：算法实现与优化

// 思路： // 1. 根据输入构建初始链表 // 2. 根据插入操作，在链表中插入新节点 // 3. 顺序输出链表中的元素

#include #include

using namespace std;

class ListNode { public: int val; ListNode* next; ListNode(int x) : val(x), next(NULL) {} };

// 构建初始链表 ListNode* buildLinkedList(vector& nums) { ListNode* dummy = new ListNode(-1); ListNode* cur = dummy; for (int i = 0; i < nums.size(); i++) { cur->next = new ListNode(nums[i]); cur = cur->next; } return dummy->next; }

// 在链表中插入新节点 ListNode* insertNode(ListNode* head, int x, int y) { ListNode* dummy = new ListNode(-1); dummy->next = head; ListNode* cur = dummy; while (cur->next && x > 1) { cur = cur->next; x--; } ListNode* newNode = new ListNode(y); newNode->next = cur->next; cur->next = newNode; return dummy->next; }

// 顺序输出链表中的元素 void printLinkedList(ListNode* head) { ListNode* cur = head; while (cur) { cout << cur->val << ' '; // 将双引号改为单引号 cur = cur->next; } cout << endl; }

int main() { int n; cin >> n; vector nums(n); for (int i = 0; i < n; i++) { cin >> nums[i]; } ListNode* head = buildLinkedList(nums);

int m;
cin >> m;
for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    head = insertNode(head, x, y);
}

printLinkedList(head);

return 0;

}