编写删除带头结点的单链表head中所有结点值为x的结点的算法；

算法思路：

1. 定义指针p指向头结点的下一个结点，定义指针pre指向头结点；

2. 从头结点的下一个结点开始遍历单链表；

3. 若当前结点的值等于x，则删除该结点，即让pre的next指向p的next，同时释放p所指向的结点；

4. 否则，将pre和p分别向后移动一个结点；

5. 重复步骤2-4，直到p指向空结点为止。

算法实现：

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

其中，ListNode是单链表结点的结构体，包含一个int型的val成员和一个指向下一个结点的指针next成员。head是指向单链表头结点的指针。

相关问题

设计一个算法，将一个结点值为自然数的带头结点单链表拆分为两个带头结点单链表，原表中保留值为偶数的结点，而值为奇数的结点按它们在原表中的相对次序组成一个新的带头结点单链表。

算法如下：

1. 定义两个新的带头结点单链表，分别为evenList和oddList。

2. 遍历原链表，如果结点的值为偶数，则将该结点插入evenList中；如果结点的值为奇数，则将该结点插入oddList中。

3. 遍历完原链表后，将oddList插入到evenList的末尾。

4. 返回evenList和oddList。

代码实现如下：

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

pair<ListNode*, ListNode*> splitList(ListNode* head) {
    ListNode* evenList = new ListNode(0);
    ListNode* oddList = new ListNode(0);
    ListNode* evenTail = evenList;
    ListNode* oddTail = oddList;
    ListNode* cur = head->next;
    while (cur != NULL) {
        if (cur->val % 2 == 0) {
            evenTail->next = cur;
            evenTail = evenTail->next;
        } else {
            oddTail->next = cur;
            oddTail = oddTail->next;
        }
        cur = cur->next;
    }
    evenTail->next = oddList->next;
    oddTail->next = NULL;
    return make_pair(evenList, oddList);
}

编写不带头结点的单链表删除算法，完成的功能为：删除单链表head中第i个元素，并用x返回其值。

在不使用头结点的单链表中删除第i个节点可以分为以下几个步骤：

1. **初始化**：如果链表为空或者i小于1，直接返回null表示无法删除。

2. **遍历查找前i-1个节点**：创建两个指针，`current` 和 `prev`，分别用于当前节点和前一个节点。`prev` 初始设为 null，然后从头开始移动 `current`，直到找到第 i - 1 个节点，同时更新 `prev` 为 `current`。

3. **定位目标节点**：在找到了第 i - 1 个节点之后，将 `current` 指向第 i 个节点。

4. **删除目标节点**：如果 `current` 不为 null，则删除 `current` 节点。这通常通过设置 `prev.next` 为 `current.next` 来实现，因为我们要让 `prev` 的下一个节点指向 `current` 的下一个节点，跳过 `current`。

5. **返回值**：如果成功删除了节点，就返回 `current.value`；如果没有找到第 i 个节点（即 `current` 仍为 null），则说明链表太短，无法删除第 i 个元素，也返回 x。

下面是一个简单的 Python 示例：

def delete_node(head, i, x):
    if head is None or i <= 0:
        return x

    current = head
    prev = None
    for _ in range(i - 1):
        if current is None:
            return x
        prev = current
        current = current.next

    if current is not None:
        prev.next = current.next
    else:
        print(f"Error: Cannot delete element at index {i}, as the list only has {i - 1} elements.")

    # Return the value of the deleted node (if it exists)
    if current is not None:
        return current.value

# 使用示例
# 删除链表中第3个节点
head = Node(1, Node(2, Node(3, Node(4, Node(5)))))
deleted_value = delete_node(head, 3, "x")  # 返回 3