剑指OFFER之复杂链表的复制（九度OJ1524）
剑指OFFER之复杂链表的复制（九度OJ1524）
用户1154259
发布于 2018-01-18 10:44:42
发布于 2018-01-18 10:44:42
文章被收录于专栏：xingoo, 一个梦想做发明家的程序员
题目描述：
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。
输入：
输入可能包含多个测试样例，输入以EOF结束。 对于每个测试案例，输入的第一行为一个整数n (1<=n<=1000)：n代表将要输入的链表元素的个数。（节点编号从1开始）。 接下来有n个数，表示链表节点中的值。 接下来有n个数Ti，Ti表示第i个节点的另一个指针指向。 Ti = 0 表示这个指针为NULL。
输出：
对应每个测试案例， 输出n行，每行有二个数，第一个代表当前节点值，第二个代表当前节点的特殊指针的值。
样例输入：
5
1 2 3 4 5
3 5 0 2 0样例输出：
1 3
2 5
3 0
4 2
5 0 解题思路：
额，我又投机取巧了...
按照原题的意思，应该是给定了这个复杂的链表，然后每个节点先复制一个节点，在把随机的指针复制，移动随机的指针，最后跳跃连接链表，即可。
代码：
#include <stdio.h>
#include <stdlib.h>
typedef struct list{
int num;
int random_link;
}List;
typedef struct listarr{
List arr[1000];
}ListArr;
int main(){
int n,i;
while(scanf("%d",&n)!=EOF && n>=1 && n<=1000){
ListArr *a = (ListArr *)malloc(sizeof(ListArr));
a->arr[0].num=0;
a->arr[0].random_link=0;
for(i=1;i<=n;i++)
scanf("%d",&a->arr[i].num);
for(i=1;i<=n;i++)
scanf("%d",&a->arr[i].random_link);
for(i=1;i<=n;i++)
printf("%d %d\n", a->arr[i].num,a->arr[(a->arr[i].random_link)].num);
}
return 0;
}
/**************************************************************
Problem: 1524
User: xhalo
Language: C
Result: Accepted
Time:40 ms
Memory:912 kb
****************************************************************/本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2014-06-10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
