LeetCode | Copy List with Random Pointer

题目

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.

题目的难点在于随机指针的拷贝。

如下两种思路：

1. 利用map纪录原节点和拷贝节点的对应关系，纪录好后，再对指针赋值。有递归（解法1）和非递归（解法2）两种实现方法。

2. 比较巧妙的方法，只利用O(1)额外空间，遍历三次链表实现深度拷贝，具体方法参见解法3。

代码

解法1

import java.util.HashMap;
import java.util.Map;


public class CopyListWithRandomPointer {
	class RandomListNode {
		int label;
		RandomListNode next, random;

		RandomListNode(int x) {
			this.label = x;
		}
	}


	public RandomListNode copyRandomList(RandomListNode head) {
		Map
  
    map = new HashMap
   
    (); map.put(null, null); return solve(head, map); } public RandomListNode solve(RandomListNode head, Map
    
      map) { if (map.containsKey(head)) { return map.get(head); } RandomListNode node = new RandomListNode(head.label); map.put(head, node); node.next = solve(head.next, map); node.random = solve(head.random, map); return node; } }
    
   
  

解法2

import java.util.HashMap;
import java.util.Map;

public class CopyListWithRandomPointer {
	class RandomListNode {
		int label;
		RandomListNode next, random;

		RandomListNode(int x) {
			this.label = x;
		}
	}

	public RandomListNode copyRandomList(RandomListNode head) {
		if (head == null) {
			return null;
		}

		// copy the label, and record the map relation
		Map
  
    map = new HashMap
   
    (); RandomListNode p = head; while (p != null) { RandomListNode copyNode = new RandomListNode(p.label); map.put(p, copyNode); p = p.next; } // copy the pointer map.put(null, null); p = head; while (p != null) { RandomListNode copyNode = map.get(p); copyNode.next = map.get(p.next); copyNode.random = map.get(p.random); p = p.next; } return map.get(head); } }
   
  

public class CopyListWithRandomPointer {
	class RandomListNode {
		int label;
		RandomListNode next, random;

		RandomListNode(int x) {
			this.label = x;
		}
	}

	public RandomListNode copyRandomList(RandomListNode head) {
		if (head == null) {
			return null;
		}

		// 1 pass: duplicate nodes one by one and link each after original one,
		// thus building a list of 2*length.
		RandomListNode p = head;
		while (p != null) {
			RandomListNode node = new RandomListNode(p.label);
			node.next = p.next;
			node.random = p.random;
			p.next = node;
			p = node.next;
		}

		// 2 pass: set random pointer of duplicated nodes to random.next which
		// points to duplicated nodes.
		p = head;
		while (p != null) {
			p = p.next;
			if (p.random != null) {
				p.random = p.random.next;
			}
			p = p.next;
		}

		// 3 pass: construct the new list by using only duplicated nodes.
		p = head;
		RandomListNode copyHead = head.next;
		RandomListNode q = copyHead;
		while (q.next != null) {
			p.next = q.next;
			q.next = q.next.next;
			p = p.next;
			q = q.next;
		}
		p.next = null;

		return copyHead;
	}
}