题意:把链表按规则调整,使小于0的先输出,然后输出键值在[0,k]的,最后输出键值大于k的。
思路:利用vector<Node> v,v1,v2,v3。遍历链表,把小于0的push到v1中,把[0,k]的push到v2中,把大于k的push到v3中,最后把v1,2,3中的按顺序push到v中,在顺序输出v就好了。【注意点】:给出的n个结点不一定都是链表的结点,我在第一遍做的时候,在最后遍历v输出结果时,for循环写成了 ;i<n;i++) ,因为我想链表的结点个数不就是n嘛,结果有一个测试点过不去,想了许久才发现这个坑,在做链表类型的题时,这个坑一定引起重视,又如1052 Linked List Sorting。
代码:
#include <cstdio> #include <vector> using namespace std; ; struct Node{ int data; int addr,next; }LinkList[maxn]; int main() { int head,n,k; scanf("%d%d%d",&head,&n,&k); int addr,data,next; ;i<n;i++){ scanf("%d%d%d",&addr,&data,&next); LinkList[addr].addr=addr; LinkList[addr].data=data; LinkList[addr].next=next; } vector<Node> v1,v2,v3,v; int p=head; ){ ) v1.push_back(LinkList[p]); else if(LinkList[p].data>k) v3.push_back(LinkList[p]); else v2.push_back(LinkList[p]); p=LinkList[p].next; } for(auto it:v1) v.push_back(it); for(auto it:v2) v.push_back(it); for(auto it:v3) v.push_back(it); ;i<v.size();i++){//注意这里不能写成i<n!!! ) printf(].addr); else printf("%05d %d -1\n",v[i].addr,v[i].data); } ; }