数据结构练习笔记——删除单链表中某区间的数

删除单链表中某区间的数

【问题描述】已知某带头结点的单链表中存放着若干整数，请删除该单链表中元素在[x, y]之间的所有结点，
要求算法的时间复杂度为O(n)，空间复杂度为O(1)。
【输入形式】
​ 第一行：单链表中元素个数m
​ 第二行：单链表中的m个整数
​ 第三行：要删除的元素值所在区间[x,y]对应的x和y
【输出形式】除元素后的单链表中剩下的元素值
【样例输入】
​ 5
​ 13 24 50 33 56
​ 30 50
【样例输出】13 24 56

#include  <iostream>
using  namespace  std;
struct  Node  {
	int  data;
	Node  *next;
};
typedef  Node  *LinkList;
void  createList(LinkList  &L,int  n)  {
	Node  *p,*r;
	L=new  Node;
	L->next=NULL;
	r=L;
	for(int  i=1;  i<=n;  i++)  {
		p=new  Node;
		cin>>p->data;
		r->next=p;
		r=p;
	}
	r->next=NULL;
}
void  printList(LinkList  L)  {
	Node  *p;
	p=L->next;
	while(p)  {
		cout<<p->data<<"  ";
		p=p->next;
	}
	cout<<endl;
}
//----------------------------
void delElem(LinkList L, int x, int y) {
    Node *p,*q;
    p=L;
    while(p->next) {
        if(p->next->data>=x&&p->next->data<=y) {
            q=p->next;
            p->next=q->next;
            delete q;
        } else {
            p=p->next;
        }
    }
}
//----------------------------
int  main()  {
	LinkList  L;
	int  m;
	int  x,y;
	cin>>m;//单链表中元素个数
	createList(L,m);//尾插入法创建带头节点的单链表
	cin>>x>>y;//要删除的元素值所在区间[x,y],包含x和y
	delElem(L,x,y);//删除单链表中x-y之间的数
	printList(L);//输出结果单链表中的所有数据
	return  0;
}

记录一些数据结构学习过程的习题代码，便于日后查看。如有错误，欢迎交流指正。