LeetCode //C - 138. Copy List with Random Pointer

这篇具有很好参考价值的文章主要介绍了LeetCode //C - 138. Copy List with Random Pointer。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

138. Copy List with Random Pointer

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

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.
Your code will only be given the head of the original linked list.
 

Example 1:

LeetCode //C - 138. Copy List with Random Pointer,LeetCode,leetcode,c语言,算法

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

LeetCode //C - 138. Copy List with Random Pointer,LeetCode,leetcode,c语言,算法

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

LeetCode //C - 138. Copy List with Random Pointer,LeetCode,leetcode,c语言,算法

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Constraints:
  • 0 <= n <= 1000
  • − 1 0 4 < = N o d e . v a l < = 1 0 4 -10^4 <= Node.val <= 10^4 104<=Node.val<=104
  • Node.random is null or is pointing to some node in the linked list.

From: LeetCode
Link: 138. Copy List with Random Pointer


Solution:

Ideas:

The main challenge in this problem is to create a deep copy of the linked list while preserving the random pointer relations between nodes. The solution uses a mapping between the original nodes and their copies to ensure that the next and random pointers in the copied list point to the appropriate nodes.

Steps:
1. Count the Nodes:

  • Before copying the nodes, we traverse the original list to count the number of nodes. This count helps us allocate memory for our mapping structures.

2. Initialize Mapping Structures:

  • We use two arrays: oldNodes and newNodes.
  • oldNodes will store pointers to the original nodes.
  • newNodes will store pointers to the corresponding copied nodes.
  • The relationship between the two arrays is that the index of an original node in oldNodes will match the index of its copy in newNodes.

3. Copy Nodes & Fill Mapping Structures:

  • We traverse the original list again and for each node, we create a copy of it.
  • We add the original node to the oldNodes array and its copy to the newNodes array, ensuring they are at the same index.

4. Establish next and random Pointers:文章来源地址https://www.toymoban.com/news/detail-676964.html

  • We traverse the original list again.
  • For the next pointer of a copied node:
    • We find the index of the original node’s next pointer in the oldNodes array.
    • We then use this index to set the next pointer of the copied node to point to the appropriate node in the newNodes array.
  • Similarly, for the random pointer:
    • We find the index of the original node’s random pointer in the oldNodes array.
    • We then use this index to set the random pointer of the copied node to point to the appropriate node in the newNodes array.
Code:
/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
    if (head == NULL) return NULL;

    struct Node* curr = head;
    int count = 0;

    // Count nodes
    while (curr) {
        count++;
        curr = curr->next;
    }

    struct Node* oldNodes[count];
    struct Node* newNodes[count];

    curr = head;
    int index = 0;

    // 1. Copy nodes and fill our mapping structure
    while (curr) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->val = curr->val;
        newNode->next = NULL;
        newNode->random = NULL;

        oldNodes[index] = curr;
        newNodes[index] = newNode;

        curr = curr->next;
        index++;
    }

    curr = head;
    index = 0;

    // 2. Copy next and random pointers using our mapping structure
    while (curr) {
        if (curr->next) {
            int nextIndex = 0;
            while (oldNodes[nextIndex] != curr->next) {
                nextIndex++;
            }
            newNodes[index]->next = newNodes[nextIndex];
        }
        
        if (curr->random) {
            int randomIndex = 0;
            while (oldNodes[randomIndex] != curr->random) {
                randomIndex++;
            }
            newNodes[index]->random = newNodes[randomIndex];
        }

        curr = curr->next;
        index++;
    }

    return newNodes[0];
}

到了这里,关于LeetCode //C - 138. Copy List with Random Pointer的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode-中等题】138. 复制带随机指针的链表

    这里的拷贝属于深拷贝,就是不光是拷贝值,还要拷贝其指针的引用情况。如果只是单独的单向链表,则直接可以根据next指向找到下一个结点,然后创建一个新节点复制过来,直接拷贝,但是题目中的random指针指向的节点是没有归类的,这样我们就不可能使用普通的循环来进

    2024年02月10日
    浏览(45)
  • leetcode做题笔记138. 复制带随机指针的链表

    给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 

    2024年02月07日
    浏览(39)
  • 【数据结构】[LeetCode138. 复制带随机指针的链表]

    给你一个长度为  n  的链表,每个节点包含一个额外增加的随机指针  random  ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的  深拷贝 。 深拷贝应该正好由  n  个  全新  节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的  next  指针和

    2024年02月04日
    浏览(46)
  • 力扣每日一道系列 --- LeetCode 138. 随机链表的复制

    📷 江池俊: 个人主页 🔥个人专栏: ✅数据结构探索 ✅LeetCode每日一道 🌅 有航道的人,再渺小也不会迷途。 LeetCode 138. 随机链表的复制 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的

    2024年02月04日
    浏览(44)
  • 【刷题专栏—突破思维】LeetCode 138. 随机链表的复制

    前言 随机链表的复制涉及到复制一个链表,该链表不仅包含普通的next指针,还包含random指针,该指针指向链表中的任意节点或空节点。 题目链接: LeetCode 138. 随机链表的复制 题目介绍: 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指

    2024年02月05日
    浏览(43)
  • 单链表OJ题:LeetCode--138.复制带随即指针的链表

    朋友们、伙计们,我们又见面了,本期来给大家解读一下LeetCode中第138道单链表OJ题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏 : 数据结构与算法 个  人  主  页  : stackY、 C 语 言 专 栏 : C语言:从入门到精通  Lee

    2024年02月08日
    浏览(63)
  • [LeetCode]-160. 相交链表-141. 环形链表-142.环形链表II-138.随机链表的复制

    目录 160.相交链表  题目 思路 代码  141.环形链表  题目 思路 代码 142.环形链表II 题目 思路 代码 160. 相交链表 - 力扣(LeetCode) https://leetcode.cn/problems/intersection-of-two-linked-lists/description/ 给你两个单链表的头节点  headA  和  headB  ,请你找出并返回两个单链表相交的起始节点

    2024年02月05日
    浏览(48)
  • leetcode链表题报错 runtime error: member access within null pointer of type ‘ListNode‘

    今天在做leetcode203:移除链表元素时,反复遇到了报错: runtime error: member access within null pointer of type ‘ListNode’ (solution.cpp) ,报错提示的意思是试图访问’ListNode空指针类型的成员,就浅浅记录一下修复bug的过程吧。。。。 刚开始的代码是这样的,逻辑是先建立一个头结点放

    2024年02月11日
    浏览(48)
  • leetcode - 86. Partition List

    Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions. Example 1: Example 2: Constraints: Use two list node and two tail node for smaller nodes and bigger nodes. Every time add the node

    2024年02月12日
    浏览(29)
  • LeetCode //C - 61. Rotate List

    Given the head of a linked list, rotate the list to the right by k places.   Example 1: Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3] Example 2: Input: head = [0,1,2], k = 4 Output: [2,0,1] Constraints: The number of nodes in the list is in the range [0, 500]. -100 = Node.val = 100 0 = k = 2 ∗ 1 0 9 0 = k = 2 * 10^9 0 = k = 2 ∗ 1 0 9 From: LeetCo

    2024年02月10日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包