对给定的单链表 l ,设计一个程序,删除 l 中值为 x 的结点的直接前驱结点。c描

设单链表l的结构如下：

struct ListNode {
    int val;
    ListNode *next;
};

我们可以使用两个指针p和q来遍历链表l。初始时，p指向链表的头结点，q指向p的前驱结点。

遍历链表的过程如下：
1. 若p指向的结点的值不等于x，则将q指向p，然后将p向后移动一个结点。
2. 若p指向的结点的值等于x，则将p的前驱结点q的next指针指向p的后继结点，然后释放p的内存空间，最后将p向后移动两个结点。

以下是具体的实现代码：

void deletePredecessor(ListNode *l, int x) {
    if (l == NULL || l->next == NULL) return;
    
    ListNode *p = l->next;
    ListNode *q = l;
    
    while (p != NULL) {
        if (p->val == x) {
            ListNode *temp = p;
            q->next = p->next;
            p = p->next;
            delete temp;
        } else {
            q = p;
            p = p->next;
        }
    }
}

这个算法的时间复杂度是O(n)，其中n是链表长度。

相关问题

对给定的单链表 L ，设计一个算法，删除 L 中值为 x 的结点的直接前驱结点。C语言

struct ListNode {
int val;
struct ListNode *next;
};

void deletePreNode(struct ListNode *head, int x) {
struct ListNode *p = head;
while (p->next != NULL) {
if (p->next->val == x) {
struct ListNode *pre = p->next;
p->next = pre->next;
free(pre);
return;
}
p = p->next;
}
}

对给定的单链表 L ，设计一个算法，删除 L 中值为 x 的结点的直接前驱结点的c语言代码

以下是删除 L 中值为 x 的结点的直接前驱结点的 C 语言代码：

struct ListNode* deletePredecessor(struct ListNode* head, int x) {
    struct ListNode* curr = head;
    struct ListNode* prev = NULL;
    while (curr != NULL) {
        if (curr->next != NULL && curr->next->val == x) {
            if (prev == NULL) {
                head = curr->next;
            } else {
                prev->next = curr->next;
            }
            free(curr);
            break;
        }
        prev = curr;
        curr = curr->next;
    }
    return head;
}