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

算法如下：

1. 创建一个新结点y，将y的数据域设置为x。
2. 遍历链表L，找到元素x所在的结点p和其前驱结点pre。
3. 将pre的next指针指向y，将y的next指针指向p。
4. 返回修改后的链表L。

C++代码实现如下：

void insertNode(ListNode* L, int x, int y) {
    ListNode* p = L->next;
    ListNode* pre = L;

    while (p != NULL && p->data != x) {
        pre = p;
        p = p->next;
    }

    ListNode* newNode = new ListNode(y);
    pre->next = newNode;
    newNode->next = p;
}

相关问题

有n个记录存储在带头结点的单链表中,设计算法实现简单选择排序

简单选择排序是一种简单直观的排序方法，它的基本思想是每次从待排序的数据中选择最小（最大）的元素，放到已经排好序的数据的末尾（或者开头）。对于一个带头结点的单链表，实现简单选择排序的算法可以参照以下步骤：

1. 遍历链表，找到链表中的最小节点，并将其与头结点的下一个节点进行交换，即让最小节点成为新的头结点。
2. 将头结点指向的节点作为当前链表的起始节点。
3. 在剩余的链表中继续找到最小的节点，并将其插入到已排序部分的末尾。
4. 不断重复步骤1和步骤2，直到链表中的所有节点都排好序为止。

这样就完成了简单选择排序算法对单链表的排序过程。这种排序算法的时间复杂度为O(n^2)，空间复杂度为O(1)。在实际应用中，简单选择排序虽然效率不如快速排序等高级排序算法，但由于实现简单，适合对小规模数据进行排序，因此仍具有一定的实用价值。

试写出一个采用单链表存储的线性表A（A带表头结点Head）的数据元素逆置的算法。

可以使用头插法实现单链表的逆置，具体算法如下：

1. 定义三个指针变量p、q、r，分别指向头结点、第一个结点和第二个结点。

2. 将p指向头结点，q指向第一个结点，r指向第二个结点。

3. 将q的next指针指向p，即将第一个结点插入到头结点之后。

4. 将p、q、r依次向后移动一个结点，即p指向q，q指向r，r指向r的next。

5. 重复步骤3和4，直到r指向空结点，此时单链表逆置完成。

下面是具体的代码实现：

void reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return;
}
ListNode* p = head;
ListNode* q = head->next;
ListNode* r = q->next;
p->next = NULL;
while (r != NULL) {
q->next = p;
p = q;
q = r;
r = r->next;
}
q->next = p;
head->next = q;
}