struct Node { int value ; struct Node *next ; struct Node *random ; }其中,random指向该链表的任意一个节点或者NULL,请编程实现该链表的深拷贝。
Node *deepCopy (Node *head)
//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;
}
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; }
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;
}
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); } }
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; }
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; }
/* * 程序用来复制一个复杂链表 * 复杂链表表示:存在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; } }
# 花生的方法,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
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; }//未经测试,有误见谅