面试题26 复杂链表的复制-白红宇

面试题26 复杂链表的复制

阅读量：2400 次

发布时间：2019-05-10

本文共 2244 字，大约阅读时间需要 7 分钟。

题目地址：

题目1524：复杂链表的复制

题目描述：

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。

输入：

输入可能包含多个测试样例，输入以EOF结束。

对于每个测试案例，输入的第一行为一个整数n (1<=n<=1000)：n代表将要输入的链表元素的个数。（节点编号从1开始）。

接下来有n个数，表示链表节点中的值。

接下来有n个数Ti，Ti表示第i个节点的另一个指针指向。

Ti = 0 表示这个指针为NULL。

输出：

对应每个测试案例，

输出n行，每行有二个数，第一个代表当前节点值，第二个代表当前节点的特殊指针的值。

样例输入：

1 2 3 4 5

3 5 0 2 0

样例输出：

1 3

2 5

3 0

4 2

5 0

解题思路：

1、使用map<int, listNode*>，将节点序号和当前节点的指针映射到map中。

2、根据 Ti 所指向的 next_2 节点序号，将节点指针取出并赋值给当前节点的 next_2。

注意

输出 p->next_2 ->data 时，需先判断 p->next_2 是否为空。

若 p->next_2 为 NULL，则不存在 p->next_2 ->data ，应另行输出0.

#include 
   
    #include 
    
     #include 
     using namespace std;int buf[1001];struct listNode {    int data;    listNode *next_1;    listNode *next_2;};map
      
        mapNext;listNode *setNext_2(listNode *head) {    if (head == NULL)        return NULL;    listNode *p = head;    int i = 1;    listNode *q = NULL;    while(p != NULL) {        q = mapNext[buf[i ++]];        p->next_2 = q;        p = p->next_1;    }    return head;}void printNode(listNode *head) {    if(head == NULL)        return;    while(head != NULL) {        int temp = 0;        if (head->next_2 == NULL) { // head->next_2 为NULL时不能直接输出head->next_2->data            printf("%d %d\n", head->data, temp);        } else {            printf("%d %d\n", head->data, head->next_2->data);        }        head = head->next_1;    }}int main() {    int n;    while(scanf("%d", &n) != EOF) {        listNode *head, *q;        head = q = NULL;        mapNext[0] = NULL;        for (int i = 0; i < n; i ++) {            listNode *p = (listNode *)malloc(sizeof(listNode));            scanf("%d", &(p->data));            if (q == NULL) {                q = p;                head = q;            }            else {                q->next_1 = p;                q = p;            }            mapNext[i + 1] = q;        }        q->next_1 = NULL; // 链表末尾赋值为NULL        for (int i = 0; i < n; i ++) {            scanf("%d", &buf[i + 1]);        }        head = setNext_2(head);        printNode(head);    }    return 0;}/**************************************************************    Problem: 1524    Language: C++    Result: Accepted    Time:40 ms    Memory:1164 kb****************************************************************/

转载地址：http://vesob.baihongyu.com/

你可能感兴趣的文章