OF35-复杂链表的复制

题目描述

https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof

请实现 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 。

注意：本题与主站 138 题相同：https://leetcode.cn/problems/copy-list-with-random-pointer/

思路分析

负责链表的复制分为3个步骤

第1步：在每个节点的后面都复制插入一个节点

第2步：根据第一个节点更新后面一个节点的 Random 链接， Random链接即为原Node的Random链接的next节点

第3步：拆分节点，返回第二个节点

实现代码

csharp

/*
// Definition for a Node.
public class Node {
    public int val;
    public Node next;
    public Node random;
    
    public Node(int _val) {
        val = _val;
        next = null;
        random = null;
    }
}
*/

public class Solution {
    public Node CopyRandomList(Node head) {
        // 判断空(边界条件提前处理)
        if(head == null){
            return head;
        }
        // Insert Node
        Node cur = head;
        while(cur != null){
            Node node = new Node(cur.val);
            node.next = cur.next;
            cur.next = node;
            //move to next
            cur = cur.next.next;
        }
        // Update Random Link
        cur = head;
        while(cur != null ){
            if(cur.random != null){
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        // Split Node
        cur = head;
        Node resultHead = cur.next;
        Node cur2 = resultHead;
        while(cur != null ){
            cur.next = cur.next.next;
            cur = cur.next;
            if(cur2.next != null){
                cur2.next = cur2.next.next;
                cur2 = cur2.next;
            }
        }
        return resultHead;
    }
}

OF35-复杂链表的复制 #

题目描述 #

思路分析 #

实现代码 #

OF35-复杂链表的复制

题目描述

思路分析

实现代码