一开始用Java哈希表写, 不出所料超时了
遂改为C用大数组模拟链表。
C代码
#include <stdio.h>
typedef struct linkNode
{
int val;
int next;
}node;
node Link[100001];//题目数据量最大为100000
//数据的输入
void Input(int N){
int address, val, next;
for(int i=0; i<N; i++){
scanf("%d %d %d", &address, &val, &next);
Link[address].next = next;
Link[address].val = val;
}
}
//逆转链表
int reverse(int start){
int curr, temp;
curr = Link[start].next;
Link[start].next = -1;
while(curr != -1){
temp = Link[curr].next;
Link[curr].next = start;
start = curr;
curr = temp;
}
return start;
}
//获取长度
int getLen(int start){
int len = 0;
while(start != -1){
len++;
start = Link[start].next;
}
return len;
}
int Merge(int head1, int head2, int N){
int len = getLen(head1);
if(len > N/3){//维护head1链表为较短的那一条
int temp = head1;
head1 = head2;
head2 = temp;
}
head1 = reverse(head1);//将head1链表反转
//合并部分
int curr, temp;
curr = Link[head2].next;
while(head1 != -1){
temp = head1;
head1 = Link[head1].next;
Link[temp].next = Link[curr].next;
Link[curr].next = temp;
curr = Link[temp].next;
curr= Link[curr].next;//curr向后移三步
}
return head2;
}
//打印链表
void PrintLink(int start){
while(start != -1){
printf("%05d ", start);
printf("%d ", Link[start].val);
if(Link[start].next == -1){
printf("-1\n");
}else{
printf("%05d\n", Link[start].next);
}
start = Link[start].next;
}
}
int main(void){
int head1, head2, N;
scanf("%d %d %d", &head1, &head2, &N);
Input(N);
PrintLink(Merge(head1, head2, N));
}