leetCode解题报告之Copy List with Random Pointer

た入场券 2022-08-26 01:22 201阅读 0赞

**题目：**

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

Return a deep copy of the list.

**分析：**

我们知道如果是简单的copy List 的话，那么我们只需要从头到尾遍历下来，new出对应个数的Node，并把它们的连接关系设置好就可以了，但是这道题目中每个节点Node出现了Random属性，也就意味着可能当前结点Node所依赖的那个Random对应的结点还没有被创建出来。

**解题思路：**

为了解决“分析”里提到的问题，我们需要做如下三步处理！

**1. 在OldList中的每个结点后，插入一个CopyNode，这个结点的Random域和Next域与OldList中的被拷贝Node的Random域和Next一致，然后让被拷贝结点的Next域指向CopyNode结点，这样先创建出OldList中结点对应的CopyNode结点。**

**2. 由于所有的CopyNode都已经创建出来了，我们就可以调整这些CopyNode真正的Random域的值了。**

**3. 调整所有CopyNode的Next域的值，恢复OldList所有Node的Next的值到初始状态！**

**图解：**

![SouthEast][]

**AC代码：**

package copylist;
    class RandomListNode {
        int label;
        RandomListNode next, random;
        RandomListNode(int x) { this.label = x; }
    };
    
    public class Solution {
        public RandomListNode copyRandomList(RandomListNode head) {
        	
        	if (head == null)
        		return head;
        	/*第一步:在OldList的每个节点后面都插入一个copyNode(拷贝链表的结点)*/
        	RandomListNode nowNode = head;
        	while (nowNode != null){
        		RandomListNode copyNode = new RandomListNode(nowNode.label);
        		copyNode.random = nowNode.random;
        		copyNode.next = nowNode.next;
        		nowNode.next = copyNode;
        		nowNode = nowNode.next.next;
        	}
        	
        	/*第二步:确定NewList的每个节点,真正关联到的Random结点是哪个，
        	 * 		因为第一步已经把所有NewList上的结点都建立了*/
        	nowNode = head;
        	while (nowNode != null){
        		if (nowNode.random != null){
        			nowNode.next.random = nowNode.random.next;
        		}
        		nowNode = nowNode.next.next;
        	}
        	
        	/*第三步：还原OldList的next为一开始的next结点
        	 * 		并拼接NewList的next到它真正所应该关联的next结点
        	 * 		即：保持老链表OldList不变，拼接新链表NewList！
        	 * */
        	RandomListNode pHead = new RandomListNode(0);
        	pHead.next = head;
        	RandomListNode newlist = pHead;
        	
        	nowNode = head;
        	while (nowNode != null){
        		pHead.next = nowNode.next;
        		nowNode.next = pHead.next.next;
        		pHead = pHead.next;
        		nowNode = nowNode.next;
        	}
        	return newlist.next;
        }
    }

[SouthEast]: /images/20220824/930db04a22bb4a13b030d1397ce77bef.png

发表评论取消回复

表情：

评论列表（有 0 条评论，201人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 138. Copy List with Random Pointer | 138. 复制带随机指针的链表（复杂链表的复制）

题目 [https://leetcode.com/problems/copy-list-with-random-pointer/][https_leetcode.com_

朴灿烈づ我的快乐病毒、/ 2022年08月31日 09:55/ 0 赞/ 147 阅读

相关 leetCode解题报告之Gas Station

题目： There are N gas stations along a circular route, where the amount of gas at station

偏执的太偏执、/ 2022年08月26日 04:45/ 0 赞/ 115 阅读

相关 leetCode解题报告之Copy List with Random Pointer

题目： A linked list is given such that each node contains an additional random pointer wh

た入场券/ 2022年08月26日 01:22/ 0 赞/ 202 阅读

相关 leetCode解题报告之Reorder List

题目： Given a singly linked list L: L0→L1→…→Ln\-1→Ln, reorder it to: L0→Ln→L1→Ln\-1→L2→

素颜马尾好姑娘i/ 2022年08月26日 00:45/ 0 赞/ 172 阅读

相关 leetCode解题报告之Insertion Sort List

题目： Sort a linked list using insertion sort. 分析：这个题目是想要让我们来做一个链表的插入排序问题. 这样

曾经终败给现在/ 2022年08月25日 15:44/ 0 赞/ 176 阅读

相关 LeetCode138—Copy List with Random Pointer

原题 [原题链接][Link 1] > A linked list is given such that each node contains an additiona

小灰灰/ 2022年07月18日 09:07/ 0 赞/ 120 阅读

相关 leetcode 138. Copy List with Random Pointer 链表复制 + HashMap

A linked list is given such that each node contains an additional random pointer which c

￡神魔★判官ぃ/ 2022年06月08日 06:00/ 0 赞/ 123 阅读

相关 [Leetcode][python]Copy List with Random Pointer/复制带随机指针的链表

题目大意一个链表中的每一个节点都有一个额外的随机指针，指向链表中的任意节点或空节点。对这个链表进行深拷贝。（要拷贝随即指针）解题思路有两种思路，参考：

淡淡的烟草味﹌/ 2022年06月05日 07:06/ 0 赞/ 118 阅读

相关 LeetCode刷题笔记（链表）：copy-list-with-random-pointer

-------------------- 转载请注明作者和出处：[http://blog.csdn.net/u011475210][http_blog.csdn.net

雨点打透心脏的1/2处/ 2022年06月01日 01:38/ 0 赞/ 123 阅读

相关【Leetcode】138. Copy List with Random Pointer（链表拷贝）（剑指offer原题）

A linked list is given such that each node contains an additional random pointer which c

谁借莪１个温暖的怀抱￠/ 2022年02月09日 08:53/ 0 赞/ 143 阅读