每日一题:复制带随机指针的链表(LeetCode 138)

题目

复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
示例 :
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

解答

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == NULL) return NULL;

        Node* cur = head;
        unordered_map<Node*, Node*> mapNode;
        //遍历原链表,创建新节点并使用哈希表记录新旧结点的关系
        while(cur != NULL)
        {
            //原结点为key,新节点为value
            mapNode[cur] = new Node(cur->val);
            //继续遍历链表
            cur = cur->next;
        }

        cur = head;
        //再次遍历原链表
        while(cur != NULL)
        {
            //通过map获取新结点的Next,并赋值给新节点的next
            mapNode[cur]->next = mapNode[cur->next];
            //通过map获取新结点的random,并赋值给新节点的random
            mapNode[cur]->random = mapNode[cur->random];
            cur = cur->next;
        }

        return mapNode[head];
    }
};
扫描关注程序区
THE END
分享
二维码
打赏
海报
每日一题:复制带随机指针的链表(LeetCode 138)
题目 复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。 示例 : ……
<<上一篇
下一篇>>