2、 试写一个算法,在带头结点的单链表L的元素x前插入一个结点y

算法如下：

输入：带头结点的单链表L，元素x，结点y
输出：在元素x前插入结点y的单链表L

1. 创建一个新结点p，将结点y的数据域赋值给p的数据域，将p的指针域指向空。
2. 从头结点开始遍历单链表L，寻找元素x所在的结点pre以及元素x所在的结点pos。
3. 如果找到了元素x所在的结点pos，则将pre的指针域指向新结点p，将新结点p的指针域指向pos。
4. 如果没有找到元素x所在的结点pos，则在链表末尾插入新结点p。

代码实现（C++）：

void insertNode(ListNode* L, int x, int y) {
    ListNode* p = new ListNode(y); // 创建新结点p，赋值为y
    ListNode* pre = L; // pre指向头结点
    ListNode* pos = L->next; // pos指向首个元素结点
    while (pos != NULL && pos->val != x) { // 寻找元素x所在的结点pre和pos
        pre = pos;
        pos = pos->next;
    }
    if (pos != NULL) { // 如果找到了元素x所在的结点pos
        pre->next = p; // 将pre的指针域指向新结点p
        p->next = pos; // 将新结点p的指针域指向pos
    } else { // 如果没有找到元素x所在的结点pos
        pre->next = p; // 在链表末尾插入新结点p
        p->next = NULL;
    }
}