1397 链表的插入和删除II

时间限制 : 2000/1000 MS(Java/Others) | 内存限制 :65536/32768 KB(Java/Others)

提交数 : 923 | 通过数 : 388

题目描述

给定一串数字然后给定若干插入和删除操作，将操作后的结果输出。

输入要求

第一行：n这串数字有n个（n>=1) 第二行：n个数字表示这串数字第三行：m表示有m个操作后面m行：I a b c1 c2...cb（在第a个数字后插入b个数c1到cb）|D a b（删除第a到b个数字，包括b）数字从1开始

输出要求

操作后的结果。每个数字用空格空开

输入样例

3
2 1 3
2
D 3 3
I 1 5 1 2 3 4 5

输出样例

2 1 2 3 4 5 1

#include<bits/stdc++.h>
using namespace std;
typedef struct S{
	int id;
	struct S *next;
}stu;
stu* init()
{
	stu*p=(stu*)malloc(sizeof(stu));
	p->id=0;
	p->next=NULL;
	return p;
}
void endinsert(stu*head,int date)
{
	stu*p=head;
	while(p->next!=NULL)
	{
		p=p->next;
	}
	stu*q=(stu*)malloc(sizeof(stu));
	q->id=date;
	q->next=p->next;
	p->next=q;
}
void insert(stu*head,int i,int j)
{
	stu*p=head->next;
	int flag=1;
	while(p!=NULL)
	{
		if(flag==i)
		{
			stu*p2=(stu*)malloc(sizeof(stu));
			p2->id=j;
			p2->next=p->next;
			p->next=p2;
		}
		else
		{
			p=p->next;
		}
		flag++;
	}
}
void print(stu*head)
{
	stu*p=head->next;
	int flag=0;
	while(p!=NULL)
	{
		flag++;
		if(flag==1)
		printf("%d",p->id);
		else
		printf(" %d",p->id);
		p=p->next;
	}
	printf("\n");
}
void delet(stu*head,int i,int j)
{
	stu*p2=head->next;
	stu*p1=head;
	int flag=1;
	while(p2!=NULL)
	{
		if(flag>=i&&flag<=j)
		{
			p1->next=p2->next;
			free(p2);
			p2=p1->next;
		}
		else
		{
			p2=p2->next;
			p1=p1->next;
		}
		flag++;
	}
}
int main()
{
	stu*head=init();
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		endinsert(head,x);
	}
	int m;
	cin>>m;
	for(int i=0;i<m;i++)
	{
		char y;
		cin>>y;
		if(y=='I')
		{
			int z,d;
			cin>>z>>d;
			vector<int> e;
			for(int i=0;i<d;i++)
			{
				int f;
				cin>>f;
				e.push_back(f);
			}
			reverse(e.begin(),e.end());
			for(int i=0;i<e.size();i++)
	       {
		       insert(head,z,e[i]);
	       }
		}
		if(y=='D')
		{
			int g,k;
			cin>>g>>k;
			delet(head,g,k);
		}
	}
	print(head);
	return 0;
 }