## Copy List with Random Pointer

07/13/2016 Hash Table Linked List

## Question

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.

## Solution

Result: Accepted Time: 224 ms

Here should be some explanations.

/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
*     int label;
*     struct RandomListNode *next;
*     struct RandomListNode *random;
* };
*/

struct RandomListNode * get_random_node(struct RandomListNode *origin,struct RandomListNode * newly,struct RandomListNode *ptr)
{
while(origin && origin != ptr)
{
origin = origin -> next;
newly = newly -> next;
}
return newly;
}
struct RandomListNode *copyRandomList(struct RandomListNode *head) {
return NULL;
{
last->next = malloc(sizeof(struct RandomListNode));
last = last->next;
last -> label = head -> label;
}
last->next = NULL;
while(last)
{
last->random = NULL;
else

• Time Complexity: $O(n^2)$
• Space Complexity: $O(1)$