假设有如下一个链表，其中，random指向该链表的任意一个节_创新工场笔试题

花生

分三步：第一步，拷贝结点，形成A-A‘-B-B’的形式

第二步:拷贝random A‘的random是A的random的next如果存在的话

第三步：拆开

发表于 2015-07-14 10:11:39 回复(2)

小虎牙

答：该题应该先实现对原链表next元素的拷贝，然后再实现对random元素的拷贝，其代码为：

//实现链表深拷贝的函数

Node *deepCopy(Node *head)

{

if(head==NULL)

return NULL;

for(Node *now=head;now;)//将原链表所有节点进行复制一次，并将复制的节点放在原节点之后

{

Node*copy=new Node(now->value);

copy->next=now->next;

now->next=copy;

now=copy ->next;

}

for(Node *now=head;now;now=now->next->next)//对random指针进行复制

{

now->next->random=(now->random==NULL)?NULL:now->random->next;

}

Node *h=head->next,*t=h,*tail=head;

for(;;)

{

tail->next=t->next;

tail=tail->next;

if(tail==NULL)

{

break;

}

t->next=tail->next;

t=t->next;

}

return h;

}

发表于 2015-12-15 10:12:35 回复(0)

低调leo

//step1. add same node to nodes in list
//step2. init the random pointer
//step3. split the list to two parts, return newNode

Node *deepCopy (Node *head) {
                    Node *p = head, *q = head->next, *newNode = NULL;
    
    //step 1
    while (p != NULL) {    
        newNode = (Node *)malloc(sizeof(Node));
        newNode->next = p->next;
        p->next = newNode;
        newNode->value = p->value;
        newNode->random = NULL;

        p = q;
        q = q->next;
    }

    //step 2
    p = head;
    q = p->next;
    while (q != NULL) {
        if (p->random != NULL)
            q->random = q->random->next;
        if (q->next == NULL)
            break;
        p = q->next;
        q = p->next;
    }  //step 3
    newNode = head->next;
    p = head; q = p->next;
    while (q != NULL) {
        p->next = q->next;
        if (q->next == NULL)
            break;
        q->next = p->next->next;

        p = p->next;
        q = q->next;
    }
    return newNode;
}

编辑于 2015-07-14 16:53:59 回复(1)

夢醒啦啦啦_Gerald

Node *deepCopy (Node *head)
{
    Node* now = head;
    Node* next = head->next;
    while( now != NULL )
    {
         Node * copy = new Node;
         copy->value = now->value;
         copy->next  = now->next;
         now ->next  = copy;
         now         = next;
         next        = next->next;
    }
    now = head;
    while( now != NULL )
    {
         now->next->random = now->random->next;
         now = now->next->next;
    }
    Node* head2 = head->next;
    Node* newHead = head->next;
    while( head2->next != NULL )
    {
        head->next = head2->next;
        head2->next = head2->next->next;
        head = head->next;
        head2 = head2->next;
    }
    
    return newHead;
}

编辑于 2015-07-14 12:18:51 回复(1)

怼你没商量

Node *deepCopy (Node *head)

{

if(head == NULL)

return head;

Node *p = head;

while(p!= NULL)

{

Node *q = new Node;

q->value = p->value;

q->random = NULL;

q->next =NULL;

q->next = p->next;

p->next = q;

p = q->next;

}

p = head;

while(p!= NULL && p->next != NULL)

{

Node *q = p->next;

if (p->random) {

q-> random = p->random->next;

}

p = q->next;

}

p = head;

Node *newHead=NULL;

Node *newNext=NULL;

while(p!= NULL)

{

Node *q = p->next;

p->next = q->next;

if(newHead == NULL)

{

newHead = q;

newNext = q;

}

else

{

newNext->next = q;

newNext = newNext->next;

}

p = p->next;

}

return newHead;

}

发表于 2016-02-26 09:47:56 回复(0)

大力水手

<div> Node *deepCopy(Node *head){ </div> <div>     <br /> </div> <div> } </div>

发表于 2015-08-15 15:16:07 回复(0)

紫竹

package conmon.niuke;

import java.util.Random;

/**假设有如下一个链表：
 * struct Node
 * {
 *     int value ;
 *    struct Node *next ;
 *     struct Node *random ;
 * }    
 *其中，random指向该链表的任意一个节点或者NULL，请编程实现该链表的深拷贝。     
 *  
 *Node *deepCopy (Node *head)   
 *  
 * @author luchunlong
 *
 * 2015年8月13日 上午10:06:39
 */
public class LinkListDeepCopy {
	
	class Node{
		int value;
		Node next;
		Node random;
		
		public Node(int value){
			this.value=value;
		}
	}
	
	/**深复制链表
	 * @param head
	 * @return
	 */
	public Node deepCopy(Node head){
		Node curr=head;
		Node copyhead=new Node(curr.value);
		Node currcopy=copyhead;
		while(curr.next!=null){                      //复制节点及值
			curr=curr.next;
			Node copy=new Node(curr.value);
			currcopy.next=copy;
			currcopy=currcopy.next;
		}
		
		curr=head;
		currcopy=copyhead;
		while(curr!=null){                          //复制random属性
			int offset=getOffsetRandom(head,curr);
			if(offset!=0){
				Node copy=copyhead;
				for(int i=0; i<offset;i++ ){
					copy=copy.next;
				}
				currcopy.random=copy;
			}else if(curr.random==head){
				currcopy.random=copyhead;
			}
			curr=curr.next;
			currcopy=currcopy.next;
		}
		
		return copyhead;
	}
	
	
	/**计算某个节点的random节点与头结点head的偏移量
	 * @param head
	 * @param itself
	 * @return
	 */
	public int getOffsetRandom(Node head,Node itself){
		int offset=0;
		Node random=itself.random;
		if(random==null) return 0;
		while(head!=null){
			if(head==random){
				break;
			}
			offset++;
			head=head.next;
		}
		return offset;
	}
	
	
	public static void main(String[] args){
		LinkListDeepCopy copyer=new LinkListDeepCopy();
		Node head=copyer.createList();
		Node copy=copyer.deepCopy(head);
		copyer.printList(head, "原来的");
		copyer.printList(copy, "复制的");
		
	}
	
	
	
	/**创建链表，并初始化
	 * @return
	 */
	public Node createList(){
		Node head=new Node(new Random().nextInt(10));;
		Node curr=head;
		for(int i=0;i<5;i++){            //生成链表
			Node newNode=new Node(new Random().nextInt(10));
			curr.next=newNode;
			curr=curr.next;
		}
		head.random=head.next;
		head.next.next.next.random=head;
		return head;
	}
	
	/**打印列表
	 * @param head
	 * @param name
	 */
	public void printList(Node head,String name){
		String list="";
		while(head!=null){
			list+="(addrs:"+head.hashCode();
			list+=",value:"+head.value;
			list+=",rando:"+(head.random==null?"":head.random.hashCode())+")-->";
			head=head.next;
		}
		list=list.substring(0, list.length()-3);
		System.out.println(name+":"+list);
	}
	
	
	

}

核心的思想是：抛开random属性不管，先复制链表结构和值。然后计算原链表的每一个节点的random属性相对于头结点的偏移量（绝对偏移量），也就是第几个元素，那么相应的，复制的链表中的该元素的random也指向第几个元素。

另外，之所以是计算绝对偏移量而不是相对偏移量（也就是某节点到该节点random属性指向的节点的相对距离），是因为，相对偏移量可以是负的，如果是负的，那就不好办了，单链表不能向反方向走

编辑于 2015-08-13 15:57:46 回复(0)

TaskMachine

Node *deepCopy(Node *head){
	if(head==NULL)	return NULL;
    Node *rhead = (Node*)malloc(sizeof(Node));
 	rhead->value = head->value;
 	Node *p, *rp;
 	rp = rhead;
 	p = head;
 	while(p->next!=NULL){
 		rp->next = (Node*)malloc(sizeof(Node));
 		rp->next->value = p->next->value;
		rp = rp->next;
		p = p->next; 
	}
	cout<<"OK"<<endl;
	rp->next = NULL;
	rp = rhead;
	p = head;
	while(p!=NULL){
		Node *temp=rp;
		if(p->random!=NULL){
			while(temp!=NULL){
				while(temp!=NULL&&temp->value!=p->random->value)	temp=temp->next;
				Node *rptemp=temp, *ptemp=p->random;
				while(rptemp!=NULL&&ptemp!=NULL&&rptemp->value==ptemp->value){
					rptemp=rptemp->next;
					ptemp=ptemp->next;
				}
				if(rptemp==NULL&&ptemp==NULL)	break;
				else temp=temp->next;
			}
			rp->random = temp;
		}
		else rp->random=NULL;
		rp = rp->next;
		p = p->next;
	}
	return rhead;
}

发表于 2015-08-03 20:43:15 回复(0)

新手请多包涵

1：题目中并没有指明random指针指向的是当前节点的之后的任意节点，所以random有可能指向当前节点之前的任意节点

2：完成不含有random指针节点的复制需要O(n)的时间复杂度

3：如果不采取空间换时间的方法，复制random指针的时间复杂度为O（n²），总体的时间复杂度为O（n²）

采取空间换时间的方法可以整体达到O（n）的时间复杂度，但是需要O（n）的空间

在进行的复制不含有random指针的节点的同时，为没一个含有random指针的节点建立一个hash table，这在进行复制random指针的时候就可以在O（1）的时间复杂度内获取节点rand指针指向的节点，整体的时间复杂度为O（n）

发表于 2015-07-27 16:10:54 回复(0)

程序猿灰灰

Node *deepCopy (Node *head){

    struct Node *copyhead;
    if(head==NULL)
        return head;

}

发表于 2015-07-24 19:11:17 回复(0)

wgh

struct Node
{
    int value ;
    struct Node *next ;
    struct Node *random ;
}
struct pair
{
	struct Node *one;
	struct Node *two;
}

Node *deepCopy(struct Node *head)
{
	vector<struct pair> pa;
	struct Node *head1 = new struct Node;
	head1->value = head->value;

	struct pair pnode;
	pnode.one = head;
	pnode.two = head1;
	pa.push_back(pnode);

	struct Node *node = head->next;
	struct Node *node1 = head1;
	while (node)
	{
		struct Node *temp = new struct Node;
		temp->value = node->value;
		temp->next = NULL;
		temp->random = NULL;
		node1->next = temp;
		
		pnode.one = node;
		pnode.two = temp;

		node = node->next;
		node1 = temp;
	}
	node = head;
	node1 = head1;
	while (node)
	{
		if (node->random == NULL)
		{
			node1->random = NULL;
		}
		else
		{
			node1->random = find(node->random,pa);
		}
		node = node->next;
		node1 = node1->next;
	}
	return head1;
}
struct Node *find(struct Node *node, vector<struct pair> &pa)
{
	for (int i=0; i<pa.size(); i++)
	{
		if (node == pa[i].one)
		{
			return pa[i].two;
		}
	}
	return NULL;
}

发表于 2015-07-15 19:20:12 回复(0)

新生

/*
 * 程序用来复制一个复杂链表
 * 复杂链表表示：存在2个指针，一个指针之后下一个节点，另外一个随机指针指向随机节点
 * 分成3步：
 * 1. 复制节点，如A-B-C 变成 A-A’-B-B’-C-C’
 * 2. 依次遍历节点A,B,C，将这些节点的随机指针与A’B’C’一致
 * 3. 分离A-B-C和A’B’C’，A’B’C’便是需要求得链表
 * */
public class copyComplexList
{
	public static RandomListNode Clone(RandomListNode pHead)
	{
		RandomListNode r1 = step1(pHead);
		step2(pHead);
		return step3(r1);
	}
	
	public static RandomListNode step1(RandomListNode pHead)
	{
		if(pHead == null)
			return null;
		RandomListNode resListNode = pHead;
		while(pHead != null)
		{
			RandomListNode node = new RandomListNode(pHead.label);
			node.next = pHead.next;
			pHead.next = node;
			node.random = null;
			pHead = node.next;
		}
		return resListNode;
	}
	
	public static void step2(RandomListNode pHead)
	{
		if(pHead == null)
			return;
		RandomListNode node = pHead;
		RandomListNode nodecopy = null;
		while(node != null)
		{
			nodecopy = node.next;
			if(node.random != null)
				nodecopy.random = node.random.next;
			node = nodecopy.next;
		}
	}
	
	public static RandomListNode step3(RandomListNode pHead)
	{
		if(pHead == null)
			return null;
		RandomListNode noderes = pHead;
		RandomListNode nodecopyres = noderes.next;
		RandomListNode node = pHead;
		RandomListNode nodecopy = node.next;
		while(node != null)
		{
			if(nodecopy.next == null)
			{
				node.next = null;
				nodecopy.next = null;
				break;
			}else
			{
				node.next = nodecopy.next;
				nodecopy.next = nodecopy.next;
			}
			node = nodecopy.next;
			nodecopy = node.next;
		}
		
		return nodecopyres;
	}
	
	public static void p(RandomListNode root)
	{
		while(root != null)
		{
			if(root.random != null)
				System.out.print(root.label + " (" + root.random.label + ") ");
			else
				System.out.print(root.label + " ");
			root = root.next;
		}
		System.out.println();
	}
}

class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

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

发表于 2015-07-14 20:11:11 回复(0)

sunsetsky

# 花生的方法，ruby语言描述


Node = Struct.new(:value, :nextNode, :random)

def deepCopy head
  # 如果为空则返回空
  return if head == nil
  # cur指向链表
  cur = head
  # 将链表拷贝成aAbB的形式
  while cur
    cur.nextNode = cur.clone
    cur = cur.nextNode.nextNode
  end
  
  cur = head
  while cur
    # 如果当前结点的random域不为空，则设置对应拷贝结点的random值
    cur.nextNode.random = cur.random.nextNode if cur.random
    cur = cur.nextNode.nextNode
  end
  # 拆开
  clone = head.nextNode
  while clone.nextNode
    clone.nextNode = clone.nextNode.nextNode
    clone = clone.nextNode
  end
  
  
  head.nextNode
end

def print head
  while head
    p head
    head = head.nextNode
  end
end

def test
  nodes = Array.new(5){|i| Node.new(i)}
  head = nodes[0]
  cur = head
  nodes[1,nodes.size].each do |el|
    cur.nextNode = el
    cur.random = nodes[rand(5)]
    cur = cur.nextNode
  end
  
  print deepCopy(head)
  # print head
end
test

编辑于 2015-07-14 15:27:29 回复(0)

小顽童

，拷贝结点，形成A-A‘-B-B’的形式

发表于 2015-07-14 14:09:28 回复(0)

ER_Plough

struct Node
{
    int value ;
    struct Node *next ;
    struct Node *random ;
    Node(int x):value(x),next(NULL),random(NULL){}
};
Node *deepCopy (Node *head)
{
    if(head=NULL)
        return NULL;
    Node *newhead=new Node(0);
    Node *newcur=newhead;
    Node *cur=head;
    Node *temp;
    map<Node*,Node*> m;
    while(cur)
    {
        temp=new Node(head->value);
        newcur->next=temp;
        newcur=newcur->next;
        m.insert(make_pair<Node*,Node*>(cur,temp));
    }
    newcur->next=NULL;
    cur=head;
    newcur=newhead->next;
    while(cur)
    {
        newcur->random=m[cur->random];
        newcur=newcur->next;
        cur=cur->next;
    }
    temp=newhead;
    newhead=newhead->next;
    delete temp;
    temp=NULL;
    return newhead;

}

//未经测试，有误见谅

发表于 2015-07-14 11:33:06 回复(0)

假设有如下一个链表，其中，random指向该链表的任意一个节

问题信息

热门推荐

相关试题