LeetCode – 138 – 赋值带随机指针的链表 – Java – 迭代实现 – 细喔~

题目

在这里插入图片描述


题目解析

在这里插入图片描述

首先题目要求我们赋值这么一个链表,新链表中 :val值完全一样,next 和 random 虽然不一样,但是指向链表中 节点的val值是一样的,而且指向的该节点的位置和源节点位置 是一样的。
简单来说,就是 新链表 和 旧链表的地址 地址是不一样的,架构上完全一样。
在这里插入图片描述


解题思维

1. 既然是深拷贝,就是把旧链表 val ,还有 next 和 random 指向的对象都要拷贝下来,只不过两者对象的地址是不同的。

2.我们先把 原链表的 val 值,以及链表节点个数拷贝下来。并且将新链表 和 旧链表连接起来。

在这里插入图片描述

3. 将原链表中的random值也“拷贝”下来

题目要求:新链表中:新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。就像我们前面演示的一样。 指向的节点也是“相同的”。
在这里插入图片描述
那么,也就是说新链表 random的指向 应该 与 旧链表的指向 “相同”。
在这里插入图片描述
在这里插入图片描述
在来我怎么将新链表的random指向 与 旧链表的 random 指向 “相同的节点”。
在这里插入图片描述

4. 将 新旧链表分割开来

在这里插入图片描述


最后附上程序

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return head;
        }
        for(Node node = head; node!=null;node =node.next.next){
            Node newNode = new Node(node.val);
            newNode.next = node.next;
            node.next = newNode;
        }

        for(Node node = head; node!=null;node = node.next.next){
            Node newNode = node.next;
            newNode.random = (node.random != null) ? node.random.next:null;
        }

        Node newHead = head.next;
        for(Node node = head;node!=null;node = node.next){
            Node newNode = node.next;
            node.next = node.next.next;
            newNode.next = (newNode.next != null) ? newNode.next.next : null;
        }
        return newHead;
    }
}

在这里插入图片描述

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码

)">
< <上一篇
下一篇>>