105.Copy List with Random Pointer-复制带随机指针的链表（中等题）

本文主要是介绍105.Copy List with Random Pointer-复制带随机指针的链表（中等题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

复制带随机指针的链表

1. 题目

   给出一个链表，每个节点包含一个额外增加的随机指针可以指向链表中的任何节点或空的节点。
   返回一个深拷贝的链表。

2. 挑战

   可否使用O(1)的空间

3. 题解

分别对Next指针和随机指针进行递归遍历。

/*** Definition for singly-linked list with a random pointer.* class RandomListNode {*     int label;*     RandomListNode next, random;*     RandomListNode(int x) { this.label = x; }* };*/
public class Solution {/*** @param head: The head of linked list with a random pointer.* @return: A new head of a deep copy of the list.*/public RandomListNode copyRandomList(RandomListNode head) {RandomListNode newHead = new RandomListNode(head.label);copynext(head,newHead);copyrandom(head,newHead);return newHead;}public void copynext(RandomListNode head,RandomListNode newHead){if (head == null){return ;}newHead.next = head.next == null?null:new RandomListNode(head.next.label);copynext(head.next,newHead.next);}public void copyrandom(RandomListNode head,RandomListNode newHead){if (head == null){return ;}newHead.random = head.random == null?null:new RandomListNode(head.random.label);copyrandom(head.next,newHead.next);}
}

Last Update 2016.10.9

这篇关于105.Copy List with Random Pointer-复制带随机指针的链表（中等题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---