LeetCode 138. 复制带随机指针的链表

我的leetcode：

我的leetcode刷题源码[github]：https://github.com/izhoujie/algorithmcii

leetcode 138. 复制带随机指针的链表

题目

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的 深拷贝。

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

• val：一个表示 node.val 的整数。
• random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  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 <= 10000
  node.random 为空（null）或指向链表中的节点。
  节点数目不超过 1000 。

来源：力扣（leetcode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

思路1-使用hashmap

思路解析：hashmap保存新建节点与原节点的对应关系；
然后再补充新节点random节点的数据；
需要使用额外的hashmap空间；

算法复杂度:

• 时间复杂度： $ {\color{magenta}{\omicron\left(n\right)}} $
• 空间复杂度： $ {\color{magenta}{\omicron\left(n\right)}} $

思路2-直接在原节点后复制新节点/增殖，然后剥离出新节点；

思路解析：

• 利用next和next.next的指向调整复制并把新节点连接到原节点的后面，紧邻复制；
• 然后复制原节点的random到新节点，复制完成后剥离出新链表；
  这里未用到额外的空间；
  算法复杂度:
• 时间复杂度： $ {\color{magenta}{\omicron\left(n\right)}} $
• 空间复杂度： $ {\color{magenta}{\omicron\left(1\right)}} $

算法源码示例

package leetcode;

import java.util.hashmap;

/**
 * @author zhoujie
 * @date 2020年5月12日 下午2:25:54 
 * @description: 138. 复制带随机指针的链表
 *
 */
public class leetcode_0138 {

}

//definition for a node.
class node_0138 {
	int val;
	node_0138 next;
	node_0138 random;

	public node_0138(int val) {
		this.val = val;
		this.next = null;
		this.random = null;
	}
}

class solution_0138 {
	/**
	 * @author: zhoujie
	 * @date: 2020年3月14日 下午5:42:59 
	 * @param: @param head
	 * @param: @return
	 * @return: node_0138
	 * @description: 1-map哈希表；
	 *
	 */
	public node_0138 copyrandomlist_1(node_0138 head) {
		if (head == null) {
			return head;
		}
		hashmap<node_0138, node_0138> map = new hashmap<node_0138, node_0138>();
		for (node_0138 node = head; node != null; node = node.next) {
			map.put(node, new node_0138(node.val));
		}
		for (node_0138 node = head; node != null; node = node.next) {
			map.get(node).next = map.get(node.next);
			map.get(node).random = map.get(node.random);
		}
		return map.get(head);
	}

	/**
	 * @author: zhoujie
	 * @date: 2020年3月14日 下午5:47:17 
	 * @param: @param head
	 * @param: @return
	 * @return: node_0138
	 * @description: 2-原地复制，在节点后复制一个节点，然后再剥离链表；
	 *
	 */
	public node_0138 copyrandomlist_2(node_0138 head) {
		if (head == null) {
			return head;
		}
		// 在原节点后复制节点 1->2->3 => 1->1`->2->2`->3->3`
		for (node_0138 node = head, copy = null; node != null; node = node.next.next) {
			copy = new node_0138(node.val);
			copy.next = node.next;
			node.next = copy;
		}
		// 把复制后的random节点链接上
		for (node_0138 node = head; node != null; node = node.next.next) {
			if (node.random != null) {
				node.next.random = node.random.next;
			}
		}
		// 原节点head的下一个几点就是新链表的头结点
		node_0138 newhead = head.next;
		// 剥离节点，一个一个间隔剥离节点
		for (node_0138 node = head, temp = null; node != null && node.next != null;) {
			temp = node.next;
			node.next = temp.next;
			node = temp;
		}
		return newhead;
	}
}