【1032】Sharing&链表题模板总结

1.题目

https://pintia.cn/problem-sets/994805342720868352/problems/994805460652113920
静态链表，找出两条链表的首个公共结点。

2.思路

基础题。最巧妙点在于设一个int型变量flag，然后2次遍历——第一次遍历第一条链表（全部结点的flag改从false改为true），第二次遍历第二条链表，如果当前结点的flag是true则马上break跳出for循环（千万别忘了break！！），当然也可以直接return就好了。
注意点：
（1）用map容易超时；输出格式用%05d——不足5位的整数的高位补0；
（2）由于scanf使用%c格式时是可以读入空格的，所以读入当前地址、数据、后继地址时，scanf的格式不能写成%d%c%d，而要写成%d %c %d。

3.代码

#include<cstdio>
#include<iostream>
#include<stdlib.h>
using namespace std;
const int maxn=100010;
struct Node{
	char data;
	int next;
	bool flag;//结点是否在第一条链表中出现	
}node[maxn];
int main(){
	for(int i=0;i<maxn;i++)
		node[i].flag=false;
	int s1,s2,n;
	int address,next;
	scanf("%d%d%d",&s1,&s2,&n);
	char data;//数据
	for(int i=0;i<n;i++){
		scanf("%d %c %d",&address,&data,&next);
		node[address].data=data;
		node[address].next=next;
	}
	int p;
	for(p=s1;p!=-1;p=node[p].next){
		node[p].flag=true;//枚举第一条链表的所有结点，令其出现次数为1
	}
	for(p=s2;p!=-1;p=node[p].next){
		//遍历第2链表，找到第一个已经在第一条链表中出现的结点
		if(node[p].flag==true) 
			break;
	}
	if(p!=-1){//如果第二条链表还没有到达结尾，说明找到了共用结点
		printf("%05\n",p);
	}else{
		printf("-1\n");
	}
	system("pause");
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
 

4.模板总结

（1）定义静态链表。
（2）for循环对静态链表的每个结点的某元素初始化。
（3）遍历链表，计数：

int p=begin,count=0;
while(p!=-1){//-1代表链表结束
	XXX=1;
	count++;
	p=node[p]->next;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
 

（4）很多时候题目给出的结点并不都是有效结点（即可能存在不在链表上的结点），对数组进行排序从而把有效结点移到数组左端。

bool cmp(Node a,Node b){
	if(a.XXX==-1||b.XXX=-1){
		//至少一个结点是无效结点，就把它放到数组后面
		return a.XXX>b.XXX;
	}else{
		//第二级排序
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/112570698