复制一个带有next和随机指针的链表，在链表上只有读权限

我需要复制一个链表与下一个和随机指针。通常，next指针指向链表中的下一个元素，而随机指针可能指向任何其他节点，甚至指向自己。如果我在任何时候都不允许修改给定的列表，那么如何做到这一点呢?列表上只有读取权限。

优雅的解决方案(线性时间，常数空间):

创建节点1、2、3…n，并将它们插入到1和2,2和3之间，等等，现在忽略random字段。所以列表中总共有2n个节点。

现在按以下方式设置新节点中random字段的值:

original.next.random = original.random.next

这是有效的，因为LHS是新创建节点的random字段，而RHS是指向任意节点副本的指针，这正是我们想要的。

现在单遍恢复原来的链表，并返回新的链表。

original.next = original.next.next;
copy.next = copy.next.next;

解决方案从这里开始

最简单的解决方案是这样的…

遍历原始链表并创建另一个链表，其节点与原始链表中的节点相同，并具有适当的next指针，指向新表的相应节点。你保持random指针现在的样子。

当你遍历列表时，你也将旧列表的节点地址/指针和新列表的节点地址/指针放在associative array (AKA map，哈希表等)上，其中旧列表的节点地址/指针是key，新列表的节点地址/指针是value。

然后遍历新列表，将每个节点中的random指针替换为与random指针相等的key对应的关联数组中的value。

哈希表可以用作关联数组，以实现时间和内存成本与原始列表中的元素数量成正比。

时间&该解的空间复杂度为O(n)。

struct node * copy(struct node * head) 
{
   struct node *dummy;
   struct node *dummy1=dummy;
   struct node *head1=head;
   struct node *map[1000000];
   while(head) {
      dummy->next=new struct node;
      map[head]=dummy->next;
      dummy->next->data=head->data;
      dummy=dummy->next;
      head=head->next
   }
   dummy=dummy1;
   head=head1;
   while(head){
      dummy->next->arb=map[head->arb];
      dummy=dummy->next;
      head=head->next;
   }
   return dummy1->next;
}

#include<stdlib.h>
#include<stdio.h>
typedef struct node_s{
int data;
struct node_s *next;
struct node_s *arbit;
} Node_s;
void free_list(Node_s * head){
if(!head) return;
Node_s * temp = head;
Node_s * next = head;
while(temp){
    next = temp->next;
    free(temp);
    temp = next;
}
}
void push_1(Node_s **head, int value){
if(*head == NULL){
    (*head) = (Node_s *)malloc(sizeof(Node_s));
    (*head)->data = value;
    (*head)->next = NULL;
}
else{
    Node_s * temp = (Node_s *)malloc(sizeof(Node_s));
    if(temp){
        temp->data = value;
        temp->next = (*head);
        *head = temp;
    }
}
}
void add_arbit(Node_s *L1, int a, int b){
 Node_s * first = L1;
 Node_s * second = L1;
 while(first){
     if(first->data == a)
         break;
     first = first->next;
 }
 while(second){
    if(second->data == b)
        break;
    second = second->next;
}
if(first)
    first->arbit = second;
}
Node_s * create_node(int val){
Node_s * temp =  (Node_s *)malloc(sizeof(Node_s));
if(temp){
    temp->data = val;
    temp->next = NULL;
}
return temp;
}
Node_s * clone(Node_s * node){
if(!node) return NULL;
Node_s * current = node;
//First insert clone nodes in original linked list.     
while(current){
    Node_s * current_next = current->next;
    current->next  =  create_node(current->data);
    current->next->next = current_next;
    current = current_next;
}
current = node;
//Now copy arbit pointer of each node to cloned list
Node_s * clone_head  = current->next;
while(current){
    Node_s * clone = current->next;
    if(current->arbit){
        clone->arbit    = current->arbit->next;
    }
    current = clone->next;
}
current = node;
//Segregate two linked list
while(current){
    Node_s * clone  = current->next;
    current->next = clone->next;
    if(clone->next){
        clone->next = clone->next->next;
    }
    current = current->next;
}
//return head pointer to the calling function
return clone_head;
}
int main(){
Node_s * L1 = NULL;
push_1(&L1,1);
push_1(&L1,2);
push_1(&L1,3);
push_1(&L1,4);
push_1(&L1,5);
push_1(&L1,6);
add_arbit(L1,1,6);
add_arbit(L1,2,5);
add_arbit(L1,3,1);
add_arbit(L1,4,2);
add_arbit(L1,5,4);
add_arbit(L1,6,3);
print_list_1(L1);
Node_s *clone_head  = clone(L1);
free_list(L1);
print_list_1(clone_head);
return 0;    
}

下面是递归解决方案(java):

public class Solution {  
    public HashMap<RandomListNode, RandomListNode> createdNode;   
    public RandomListNode copyRandomList(RandomListNode head) {  
        createdNode = new HashMap<RandomListNode, RandomListNode>();  
        return cc(head);  
    }  
    private RandomListNode cc(RandomListNode node) {  
        if(node == null)  
        {  
            return null;  
        }  
        RandomListNode newNode = new RandomListNode(node.label);  
        createdNode.put(node, newNode);          
        newNode.next = cc(node.next);  
        //now assign the random pointer  
        RandomListNode newRandom = null;  
        if(node.random != null)  
        {  
            newRandom = createdNode.get(node.random);  
        }  
        newNode.random = newRandom;  
        return newNode;      
    }  
}

下面是使用HashMap(也在java中)的解决方案:

public class Solution{  
    public RandomListNode copyRandomList(RandomListNode head) {  
        if(head == null) return null;  
        java.util.HashMap<RandomListNode, RandomListNode> map = new java.util.HashMap<RandomListNode, RandomListNode>();  
        RandomListNode copiedHead = new RandomListNode(head.label);  
        map.put(head, copiedHead);  
        for(RandomListNode cur = head.next, cpLst = copiedHead; cur != null; cur = cur.next, cpLst = cpLst.next){  
            cpLst.next = new RandomListNode(cur.label);  
            map.put(cur, cpLst.next);  
        }  
        for(RandomListNode cur = head, cpCur = copiedHead; cur != null; cur = cur.next, cpCur = cpCur.next)  
            cpCur.random = cur.random == null ? null : map.get(cur.random);  
        return copiedHead;  
    }  
}

从头节点开始，逐个创建node的副本
创建副本时，将原始节点和复制节点在哈希映射中的条目作为键，值。
在一个接一个地复制元素时创建一个新列表，因此每个节点都有一个next指针值。4.然后用新列表再次遍历原始列表以复制随机指针。我们可以得到哈希映射中每个节点的随机指针。

详细说明请访问:http://www.dscoding.com/2016/10/copy-linked-list-with-random-pointer.html

相关内容

最新更新

热门标签：