已知一个递增有序的不带头结点的单链表，设计算法从该链表删除与给定值相等的所有元素

可以回答这个问题。算法如下：

1. 定义两个指针，分别指向当前节点和前一个节点。
2. 遍历链表，如果当前节点的值等于给定值，则删除该节点。
3. 如果当前节点的值不等于给定值，则将前一个节点指向当前节点。
4. 遍历完整个链表后，返回链表头节点。

具体实现可以参考以下代码：

struct ListNode* deleteNode(struct ListNode* head, int val) {
struct ListNode *prev = NULL, *curr = head;
while (curr != NULL) {
if (curr->val == val) {
if (prev == NULL) {
head = curr->next;
} else {
prev->next = curr->next;
}
free(curr);
curr = prev == NULL ? head : prev->next;
} else {
prev = curr;
curr = curr->next;
}
}
return head;
}

相关问题

已知带头结点单链表中各结点的元素值为整形且递增有序，设计算法删除链表中所有大于mink且小于maxk的元素，并释放被删结点的空间

1. 初始化指针p为头结点，q为p的后继结点。
2. 如果q非空，则执行以下操作：
a. 如果q的元素值大于mink且小于maxk，则将p的后继结点指向q的后继结点，释放q结点的空间；
b. 否则，将p指向q，q指向p的后继结点。
3. 返回头结点。

代码实现如下：

void deleteRange(Node* head, int mink, int maxk) {
    Node* p = head;
    Node* q = p->next;
    while (q != NULL) {
        if (q->data > mink && q->data < maxk) {
            p->next = q->next;
            free(q);
            q = p->next;
        } else {
            p = q;
            q = p->next;
        }
    }
}

用c++设计算法将两个递增有序的带头结点的单链表A、B合并为一个递减有序的带头结点的单链表，并要求算法的时间复杂度为两个表长之和的数量级。并对代码进行注释

// 定义单链表的结构体
typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 合并两个递增有序的带头结点的单链表为一个递减有序的带头结点的单链表
ListNode* merge(ListNode* A, ListNode* B) {
    // 定义一个虚拟头结点，并初始化为空
    ListNode* dummy = (ListNode*) malloc(sizeof(ListNode));
    dummy->next = NULL;
    // 定义指向 A 和 B 的指针
    ListNode* p = A->next;
    ListNode* q = B->next;
    // 合并两个链表
    while (p && q) {
        if (p->val < q->val) {
            // 将 p 指向的结点插入到合并后链表的头部
            ListNode* node = p;
            p = p->next;
            node->next = dummy->next;
            dummy->next = node;
        } else {
            // 将 q 指向的结点插入到合并后链表的头部
            ListNode* node = q;
            q = q->next;
            node->next = dummy->next;
            dummy->next = node;
        }
    }
    // 将剩余的结点插入到合并后链表的头部
    while (p) {
        ListNode* node = p;
        p = p->next;
        node->next = dummy->next;
        dummy->next = node;
    }
    while (q) {
        ListNode* node = q;
        q = q->next;
        node->next = dummy->next;
        dummy->next = node;
    }
    // 释放 A 和 B 的头结点
    free(A);
    free(B);
    // 返回合并后的链表
    return dummy;
}

时间复杂度分析：

由于 A 和 B 都是递增有序的链表，因此在合并时只需要比较 A 和 B 的头结点，将较小的头结点插入到合并后链表的头部即可。因此，时间复杂度为 O(m+n)，其中 m 和 n 分别为 A 和 B 的长度。由于题目要求时间复杂度为两个表长之和的数量级，因此满足要求。