Java for LeetCode 138 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.

解题思路：

我们在Java for LeetCode 133 Clone Graph题中做过图的复制，本题和图的复制十分类似，JAVA实现如下：

    public RandomListNode copyRandomList(RandomListNode head) {

		if (head == null)

			return null;

		HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();

		RandomListNode node = new RandomListNode(head.label);

		RandomListNode headTemp = head, nodeTemp = node;

		map.put(head, node);

		while (headTemp.next != null) {

			nodeTemp.next = new RandomListNode(headTemp.next.label);

			map.put(headTemp.next, nodeTemp.next);

			headTemp = headTemp.next;

			nodeTemp = nodeTemp.next;

		}

		headTemp = head;

		nodeTemp = node;

		while (headTemp!= null) {

			if(map.containsKey(headTemp.random))

				nodeTemp.random=map.get(headTemp.random);

			headTemp = headTemp.next;

			nodeTemp = nodeTemp.next;

		}

		return node;

    }

巴特西

Java for LeetCode 138 Copy List with Random Pointer

最新文章

热门文章