网络异常，图片无法展示
|
请实现 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 <= 10000Node.random为空（null）或指向链表中的节点。- 节点数目不超过 1000 。
注意： 本题与主站 138 题相同：leetcode-cn.com/problems/co…
复制一个普通的链表很简单，本题的难点在于被复制链表每一个节点有一个 random 指针，指向链表中任意一个节点或者 null
对于这种情况应该如何复制原链表呢？
解题思路如下：
本题解题思路如下：
- 首先特殊判断如果传入链表为
null,返回null - 在原链表的每个节点后面复制一个新的节点，新节点的
val等于被复制的节点的val - 将复制节点的
random指针指向被复制链表节点的random指针的next,如果被复制节点的random指针指向null,则复制节点的random指针同样指向null - 将复制节点从原链表拆分成为单独的链表，即为复制后的链表
- 返回复制后链表的头节点即可
整体过程如下：
网络异常，图片无法展示
|
代码如下：
var copyRandomList = function(head) { // 特判 if(head === null) return null; let pre = head,next = pre.next; // 复制节点 while(pre){ pre.next = new Node(pre.val); pre.next.next = next; pre = next; next = pre?pre.next:null; } // 处理复制后节点的random pre = head,next = pre.next; while(next){ next.random = pre.random?pre.random.next:null; pre = next.next; next = pre?pre.next:null; } // 获取结果链表的头节点 const res = head.next; // 拆分链表 pre = head,next = pre.next; while(next){ pre.next = next.next; pre = pre.next; next.next = pre?pre.next:null; next = next.next } return res; }; 复制代码
至此我们就完成了 leetcode-剑指Offer 35-复杂链表的复制
如有任何问题或建议，欢迎留言讨论！
