66. Plus One

题目描述:

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

题目翻译

深拷贝一个链表,该链表除了含有next指针外,还包含一个random指针,该指针指向字符串中的某个节点或者为空

《剑指offer》上的面试题26

解题方案

标签: Hash Table

思路:

考虑l1作为第一个列表中的节点,l2作为第二个列表中的相应节点:

Step1 为l1的每个节点创建一个新节点来构建l2,并且将l2的相应节点后移一个位置, 于是l2中新的头节点是第二个节点

Step2 修正l2中的随机指针,记住l1-> next实际上是l2; l2-> random将是l2中的对应于l1-> random的下一个节点

Step3 将组合列表分为2个,拼接出l2的所有节点,最后返回步骤2中保存的新头节点

代码:

class Solution {
public:
    unordered_map<RandomListNode*, RandomListNode*>mp;
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode *newHead, *l1, *l2;
        if (head == NULL) return NULL;
        for (l1 = head; l1 != NULL; l1 = l1->next->next) {
            l2 = new RandomListNode(l1->label);
            l2->next = l1->next;
            l1->next = l2;
        }

        newHead = head->next;
        for (l1 = head; l1 != NULL; l1 = l1->next->next) {
            if (l1->random != NULL) l1->next->random = l1->random->next;
        }

        for (l1 = head; l1 != NULL; l1 = l1->next) {
            l2 = l1->next;
            l1->next = l2->next;
            if (l2->next != NULL) l2->next = l2->next->next;
        }

        return newHead;
    }
};

参考资料

results matching ""

    No results matching ""