题目链接地址： ?pid=1524
题目1524：复杂链表的复制
时间限制：1 秒内存限制：128 兆特殊判题：否提交：751解决：359 题目描述： 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。 输入： 输入可能包含多个测试样例，输入以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
思路分析：
对于AC这题来说，有不少方法。直接链表结点指针数组实现，，pSibling指针指向某个结点S，则从链表结点指针数组中取出S结点的地址并赋值给pSibling指针。 当然我们还是应该学习书上的那两种方法。
代码：/********************************* 【剑指Offer面试题】 九度OJ1524：复杂链表的复制Author:牧之丶 Date：2015年Email:bzhou84@163.com **********************************/#include <stdio.h>#include <stdlib.h> #include <string>#include <math.h>#include <stack>#include <vector>#include<queue> using namespace std; #define MAX 1005// 定义链表结点结构typedef struct LinkNode{ int data; LinkNode * next;// 指向链表中的当前结点的下一个结点 LinkNode * pSibling;// 特殊指针}LinkNode;LinkNode * nodeArray[MAX]; // 开一个指针数组，用于保存链表中各个的结点地址//构造带头结点的复杂链表LinkNode * createComplexLinklist(int n){ LinkNode * head = (LinkNode *)malloc(sizeof(LinkNode)); // 链表的头结点 head -> data = 0;head -> next = NULL; LinkNode * p = head;LinkNode * s = NULL;// 新结点 int i,data,Ti;//构造节点和指向下一个节点的指针 for(i = 1;i <= n;i++)//从1开始编号 {scanf(“%d”,&data);s = (LinkNode *)malloc(sizeof(LinkNode));s -> data = data;s -> next = p -> next;p -> next = s;p = s;nodeArray[i] = s; // 将新结点的地址保存到链表结点地址数组中 } // 构造链表结点的特殊指针值 p = head -> next; for(i = 1;i <= n;i++) {scanf(“%d”,&Ti);if(0 != Ti){p -> pSibling = nodeArray[Ti];}else{p -> pSibling = head;}p = p -> next; } return head;}/*** 打印复杂链表* @param head 复杂链表头指针* @return void*/void printComplexLinklist(LinkNode * head){LinkNode * p = head -> next;while(p != NULL){printf(“%d %d\n”,p -> data,p -> pSibling -> data);p = p -> next;}}int main(){int n;LinkNode * head = NULL;while(scanf(“%d”,&n)!= EOF ){head = createComplexLinklist(n);printComplexLinklist(head);}return 0;}/**************************************************************Problem: 1524Language: C++Result: AcceptedTime:40 msMemory:1160 kb****************************************************************/
在时光的激流中，我们总会长大。
