3. 假设有一个顺序表L，请编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，删除顺序表L中所有值为x的元素。

要在一个顺序表（数组或链表）中删除所有值为 `x` 的元素，并保持时间复杂度为 O(n) 和空间复杂度为 O(1)，你可以遍历列表，对于每个元素，如果它等于 `x`，就跳过它，继续到下一个。以下是基于数组的示例：

def remove_x_from_list(L, x):
    # 初始化两个指针，一个用于正常遍历，一个用于记录新列表长度
    i = 0
    j = 0

    # 遍历列表
    while i < len(L):
        if L[i] != x:  # 如果当前元素不是x，将其移动到新位置
            L[j] = L[i]
            j += 1
        i += 1  # 移动到下一个元素

    # 调整新列表的长度
    L = L[:j]

    return L

# 示例
L = [1, 2, 3, 4, 5, 2, 6, 2]
result = remove_x_from_list(L, 2)
print(result)  # 输出: [1, 3, 4, 5, 6]

在这个过程中，我们仅遍历了列表一次，所以时间复杂度是线性的（O(n)），并且只使用了常数级别的额外存储，所以空间复杂度是 O(1)。

相关问题

假设有一个顺序表L，请编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，删除顺序表L中所有值为x的元素。

要在保持线性时间和常量空间复杂度的前提下删除顺序表`L`中所有值为`x`的元素，我们可以遍历整个列表，遇到值不等于`x`的就将其复制到原位置，最后将最后一个元素替换为`x`以简化序列。由于只读取一次列表，并且不额外开辟空间，所以达到了所需的复杂度。

以下是Python的示例代码：

def remove_elements(L, x):
    if not L or x not in L:  # 检查列表是否为空或者`x`不在列表中
        return L  # 如果满足条件，直接返回原列表

    write_index = 0  # 记录下标，用于指向下一个非`x`的位置

    for i in range(len(L)):
        if L[i] != x:  # 如果元素不是`x`
            L[write_index] = L[i]  # 将它复制到新位置
            write_index += 1  # 移动写指针

    L[write_index] = x  # 最后将剩余空间填充为`x`

    return L[:write_index+1]  # 返回新的列表，注意截断到`x`之后的元素

# 示例：
L = [1, 2, 3, 2, 4, 2]  # 原顺序表
new_L = remove_elements(L, 2)
print("删除所有2后的列表:", new_L)

编写一个函数Sort(SqList &s),将顺序表中的元素逆置，要求算法的空间复杂度为O(1)。

要编写一个空间复杂度为 O(1) 的函数来逆序一个顺序表（也称为单链表），我们需要在原地修改链表节点的指针，而不是创建新的数据结构。这里假设我们有一个 `SqListNode` 结构体，包含整型值和指向下一个节点的指针。逆序过程可以按照以下步骤进行：

1. 首先，定义两个指针 `prev` 和 `current`，分别初始化为 `NULL` 和 `s->head`。

2. 然后，进入一个循环，条件是 `current` 不为空：
- 创建一个新的临时指针 `next`，存储当前节点 `current` 的下一个节点。
- 更新当前节点 `current` 的 `next` 指针，使其指向 `prev`。
- 将 `prev` 向前移动一位，设置为 `current`。
- 再次将 `current` 设置为 `next`，以便检查下一个节点。

3. 循环结束后，`prev` 就会成为新链表的尾部，原始的头部 `s->head` 现在是新的尾部。所以，最后将链表的头部指针 `s->head` 指向 `prev` 即可。

下面是一个示例的 C 语言实现：

void Sort(SqList &s) {
    SqListNode* prev = nullptr;
    SqListNode* current = s.head;

    while (current != nullptr) {
        SqListNode* next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    s.head = prev;
}