leetCode解题报告之Copy List with Random Pointer

た入场券 2022-08-26 01:22 194阅读 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 条评论，194人围观）

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

相关阅读

相关 138. Copy List with Random Pointer--Medium

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

「爱情、让人受尽委屈。」/ 2023年08月17日 15:58/ 0 赞/ 102 阅读

相关 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 赞/ 195 阅读

相关 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 赞/ 168 阅读

相关 leetCode解题报告之Sort List

勉励自己：坚持，谁说做工程的人不能学好算法！为面试做准备,加油！！！！！题目： Sort a linked list in O(n log n) time using c

你的名字/ 2022年08月25日 15:55/ 0 赞/ 81 阅读

相关 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 赞/ 116 阅读

相关 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 赞/ 120 阅读

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

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

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

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

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

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

相关 leetCode138.Copy List with Random Pointer

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

素颜马尾好姑娘i/ 2022年05月30日 02:39/ 0 赞/ 120 阅读

相关【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 赞/ 141 阅读