【LeetCode刷题(中等程度)】剑指 Offer 35. 复杂链表的复制

    科技2022-07-17  94

    请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。

    示例 1:

    输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出:[[7,null],[13,0],[11,4],[10,2],[1,0]] 示例 2:

    输入:head = [[1,1],[2,1]] 输出:[[1,1],[2,1]] 示例 3:

    输入:head = [[3,null],[3,0],[3,null]] 输出:[[3,null],[3,0],[3,null]] 示例 4:

    输入:head = [] 输出:[] 解释:给定的链表为空(空指针),因此返回 null。

    提示:

    -10000 <= Node.val <= 10000 Node.random 为空(null)或指向链表中的节点。 节点数目不超过 1000 。

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    思路一:利用hash_map来实现,首先将原来的节点记为N,要复制的节点记为N',构建一个hash_map<N,N'>,即可以利用N(原来链表)索引到当前链表N',那么我们在连接时,根据原来链表进行索引就可以知道要连接到哪里去了。

    /* // 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: unordered_map<Node*,Node*> hash_map; Node* copyRandomList(Node* head) { Node* cur = head; while(cur)//第一次遍历构建hast_map表 { hash_map[cur] = new Node(cur->val); cur = cur->next; } cur = head; while(cur) { hash_map[cur]->next = hash_map[cur->next]; hash_map[cur]->random = hash_map[cur->random]; cur = cur->next; } return hash_map[head]; } };

    时间复杂度:O(n) 空间复杂度:O(n)

    思路二:实际上我们可以不需要使用hashmap的辅助空间O(n),从而直接在原来链表上构建复制链表,这也是剑指offer书上本来给的思路。

    复制一个新的节点在原有节点之后,如 1 -> 2 -> 3 -> null 复制完就是 1 -> 1 -> 2 -> 2 -> 3 - > 3 -> null从头开始遍历链表,通过 cur.next.random = cur.random.next 可以将复制节点的随机指针串起来,当然需要判断 cur.random 是否存在将复制完的链表一分为二 根据以上信息,我们不难写出以下代码: /* // 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 == nullptr) return nullptr; Node* cur = head; //完成链表节点的复制 并将复制的链表间隔插入在原来链表中 while(cur) { Node* copyNode = new Node(cur->val); copyNode->next = cur->next; cur->next = copyNode; cur = cur->next->next;//转向到原来链表的下一个节点 } //完成随机链表的复制 cur = head; while(cur) { if(cur->random)//必须有才可以连接 random默认构造已经是null { //原来链表的random的下一个节点就是复制链表的random要指向的地方 cur->next->random = cur->random->next; } cur = cur->next->next;//依然是在原来链表上跳过两个节点 } //将链表再分开 Node* copyHead = head->next; cur = head; Node* curCopy = head->next; while(cur) { cur->next = cur->next->next;//将原来链表提取出来 cur = cur->next; if(curCopy->next) { curCopy->next = curCopy->next->next;//在复制链表上跳过原来节点 curCopy = curCopy->next;//跳到下一个节点 } } return copyHead; } };
    Processed: 0.011, SQL: 8