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

文章目录

题目

题目解析

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

解题思维

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

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

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

题目要求：新链表中：新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。就像我们前面演示的一样。 指向的节点也是“相同的”。

那么，也就是说新链表 random的指向 应该 与 旧链表的指向 “相同”。


在来我怎么将新链表的random指向 与 旧链表的 random 指向 “相同的节点”。

4. 将 新旧链表分割开来

最后附上程序

classSolution{publicNodecopyRandomList(Node head){if(head ==null){return head;}for(Node node = head; node!=null;node =node.next.next){Node newNode =newNode(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;}}