编写一个算法，一个线性表L采用单链存储结构，若其中所有元素为整数，删除数据值在[x,y]之间的所有元素，要求算法的时间复杂度为O(n)，空间复杂度为O(1)

1. 定义两个指针p和pre，初始时p指向第一个节点，pre指向头结点。
2. 遍历整个链表，对于每个节点，判断其数据值是否在[x,y]之间，如果是，则删除该节点，并将pre的next指向p的next。
3. 如果该节点没有被删除，则将pre指向p。
4. 将p指向p的next，继续遍历下一个节点。
5. 返回头结点的next指针，即为删除后的链表。

具体实现代码如下：

void deleteRange(Node* head, int x, int y) {
    Node* pre = head;
    Node* p = head->next;
    while (p != NULL) {
        if (p->data >= x && p->data <= y) {
            pre->next = p->next;
            delete p;
            p = pre->next;
        } else {
            pre = p;
            p = p->next;
        }
    }
}

相关问题

已知长度为 n 的线性表 A 中的元素是整数, 写算法求线性表中值大于 item 的元素个数。分两种情况编写函数: (1) 线性表采用顺序存储; (2) 线性表采用单链表存储。

(1) 线性表采用顺序存储:
算法步骤如下：
1. 初始化计数器 count=0；
2. 遍历线性表 A，对于每一个元素，若其值大于 item，则 count 加一；
3. 遍历结束后，返回 count。

C++ 代码如下:

int countGreaterThanItem(vector<int>& A, int item) {
    int count = 0;
    for(int i=0; i<A.size(); i++) {
        if(A[i] > item) {
            count++;
        }
    }
    return count;
}

(2) 线性表采用单链表存储:
算法步骤如下：
1. 初始化计数器 count=0；
2. 遍历单链表 A，对于每一个元素，若其值大于 item，则 count 加一；
3. 遍历结束后，返回 count。

C++ 代码如下：

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

int countGreaterThanItem(ListNode* head, int item) {
    int count = 0;
    ListNode* p = head;
    while(p != NULL) {
        if(p->val > item) {
            count++;
        }
        p = p->next;
    }
    return count;
}

逆位序输入线性表的n个数据元素，编写建立带头结点的单链表的算法 。

好的，下面是建立带头结点的单链表的算法：

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct Node {
    ElemType data;
    struct Node* next;
} Node, *LinkedList;

LinkedList createList(int n) {
    LinkedList head = (LinkedList)malloc(sizeof(Node)); // 创建头结点
    head->next = NULL;
    Node* tail = head; // tail 指向链表尾部

    printf("请输入 %d 个整数：\n", n);
    for (int i = 0; i < n; i++) {
        ElemType x;
        scanf("%d", &x);
        Node* p = (Node*)malloc(sizeof(Node)); // 创建新结点
        p->data = x;
        p->next = NULL;
        tail->next = p; // 将新结点插入到链表尾部
        tail = p; // 更新 tail 指针
    }

    return head;
}

void printList(LinkedList L) {
    Node* p = L->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main() {
    int n;
    printf("请输入线性表的长度：");
    scanf("%d", &n);
    LinkedList L = createList(n);
    printf("逆序输入的线性表为：");
    printList(L);
    return 0;
}

算法的主要思路是：先创建一个头结点，然后从头部依次插入新结点，形成单链表。最后输出单链表中的元素。