CareerCup

1. Insert new nodes between old ones

1->1'->2->2'->3->3'

2. For every inserted node set random is next node to random
1' -> random = 1->random->next

3. Decouple List

Let' s assume

public class Node { 	
		private Node next; 
		private Node random; 
		private String data; 
		// getters and setters omitted for the sake of brevity 
	}

Deep copy would look like

private Node deepCopy(Node original) { 
		// We use the following map to associate newly created instances 
		// of Node with the instances of Node in the original list 
		Map<Node, Node> map = new HashMap<Node, Node>(); 
		// We scan the original list and for each Node x we create a new 
		// Node y whose data is a copy of x's data, then we store the 
		// couple (x,y) in map using x as a key. Note that during this 
		// scan we set y.next and y.random to null: we'll fix them in 
		// the next scan 
		Node x = original; 
		while (x != null) { 
			Node y = new Node(); 
			y.setData(new String(x.getData())); 
			y.setNext(null); 
			y.setRandom(null); 
			map.put(x, y); 
			x = x.getNext(); 
		} 
		// Now for each Node x in the original list we have a copy y 
		// stored in our map. We scan again the original list and 
		// we set the pointers buildings the new list 
		x = original; 
		while (x != null) { 
			// we get the node y corresponding to x from the map 
			Node y = map.get(x); 
			// let x' = x.next; y' = map.get(x') is the new node 
			// corresponding to x'; so we can set y.next = y' 
			y.setNext(map.get(x.getNext())); 
			// let x'' = x.random; y'' = map.get(x'') is the new 
			// node corresponding to x''; so we can set y.random = y'' 
			y.setRandom(map.get(x.getRandom())); 
			x = x.getNext(); 
		} 
		// finally we return the head of the new list, that is the Node y 
		// in the map corresponding to the Node original 
		return map.get(original); 	
	}

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node *next;
    struct Node *random;
} Node_t;

void copy_list(Node_t *src, Node_t *dst);
void print_list(Node_t *list);
int get_index(Node_t *list, Node_t *n);

int main(int argc, char **argv)
{
    Node_t src;
    
    src.next = (Node_t *)malloc(sizeof(Node_t));
    src.next->next = (Node_t *)malloc(sizeof(Node_t));
    src.next->next->next = NULL;
    
    src.random = src.next->next;
    src.next->random = src.next;
    src.next->next->random = &src;
    
    src.data = 1;
    src.next->data = 2;
    src.next->next->data = 3;
    
    printf("SRC:\n");
    print_list(&src);
    
    Node_t dst;
    copy_list(&src, &dst);
    
    printf("DST:\n");
    print_list(&dst);
    
    dst.random->data = 7;
    
    printf("SRC:\n");
    print_list(&src);
    
    printf("DST:\n");
    print_list(&dst);
    
    /* should cleanup all dynamically allocated memory here */
    
    return 0;
}

void copy_list(Node_t *src, Node_t *dst)
{
    if (dst == NULL) return;
    
    /* copy data and next pointers before copying random pointer */
    Node_t *tmpdst = dst;
    Node_t *curnode = src;
    while (curnode != NULL)
    {
        tmpdst->data = curnode->data;
        if (curnode->next != NULL)
            tmpdst->next = (Node_t *)malloc(sizeof(Node_t));
        else
            tmpdst->next = NULL;
        
        curnode = curnode->next;
        tmpdst = tmpdst->next;
    }
    
    /* setup random pointers */
    tmpdst = dst;
    curnode = src;
    while (curnode != NULL)
    {
        if (curnode->random != NULL)
        {
            int idx = get_index(src, curnode->random);
            
            Node_t *tmpdst2 = dst;
            while (idx > 0)
            {
                tmpdst2 = tmpdst2->next;
                --idx;
            }
            
            tmpdst->random = tmpdst2;
            
        }
        else
        {
            tmpdst->random = NULL;
        }
        
        tmpdst = tmpdst->next;
        curnode = curnode->next;
    }
}

void print_list(Node_t *list)
{
    /* print data from next */
    Node_t *curnode = list;
    while (curnode != NULL)
    {
        printf("%d -> ", curnode->data);
        curnode = curnode->next;
    }
    
    printf("NULL\n");
    
    /* print data from random */
    curnode = list;
    while (curnode != NULL)
    {
        printf("%d : ", curnode->data);
        if (curnode->random == NULL)
            printf("NULL");
        else
            printf("%d", curnode->random->data);
        
        printf("\n");
        
        curnode = curnode->next;
    }
}

int get_index(Node_t *list, Node_t *n)
{
    int idx = 0;
    Node_t *curnode = list;
    while (curnode != NULL)
    {
        if (curnode == n)
            return idx;
        
        ++idx;
        curnode = curnode->next;
    }
    
    return -1;
}

Outputs:

SRC:
1 -> 2 -> 3 -> NULL
1 : 3
2 : 2
3 : 1
DST:
1 -> 2 -> 3 -> NULL
1 : 3
2 : 2
3 : 1
SRC:
1 -> 2 -> 3 -> NULL
1 : 3
2 : 2
3 : 1
DST:
1 -> 2 -> 7 -> NULL
1 : 7
2 : 2
7 : 1

The above solution is O(N^2).

One should ask, do we allow to add a field say Node* workingPtr to the Node. If yes, there is an O(N) solution.

map< Node*,Node*> mmap;
    Node *copyRandomList(Node *head) {
        if(head == NULL)    return head;
        if(mmap.find(head) != mmap.end()){
            return mmap[head];
        }
        Node* node = new Node(head->label);
        mmap[head] = node;
        node->next = copyRandomList(head->next);
        node->random = copyRandomList(head->random);
        return node;
    }

Let' s assume
public class Node {
private Node next;
private Node random;
private String data;
// getters and setters omitted for the sake of brevity
}

Deep copy would look like
private Node deepCopy(Node original) {
// We use the following map to associate newly created instances
// of Node with the instances of Node in the original list
Map<Node, Node> map = new HashMap<Node, Node>();
// We scan the original list and for each Node x we create a new
// Node y whose data is a copy of x's data, then we store the
// couple (x,y) in map using x as a key. Note that during this
// scan we set y.next and y.random to null: we'll fix them in
// the next scan
Node x = original;
while (x != null) {
Node y = new Node();
y.setData(new String(x.getData()));
y.setNext(null);
y.setRandom(null);
map.put(x, y);
x = x.getNext();
}
// Now for each Node x in the original list we have a copy y
// stored in our map. We scan again the original list and
// we set the pointers buildings the new list
x = original;
while (x != null) {
// we get the node y corresponding to x from the map
Node y = map.get(x);
// let x' = x.next; y' = map.get(x') is the new node
// corresponding to x'; so we can set y.next = y'
y.setNext(map.get(x.getNext()));
// let x'' = x.random; y'' = map.get(x'') is the new
// node corresponding to x''; so we can set y.random = y''
y.setRandom(map.get(x.getRandom()));
x = x.getNext();
}
// finally we return the head of the new list, that is the Node y
// in the map corresponding to the Node original
return map.get(original);
}

struct node {
	node *n, *r;
	int data;
};
node *copy(node *src) {
	if(!src)
		return nullptr;

	node *dst = new node({nullptr, src->r, src->data});
	src->r = dst;
	node *prev = dst;		

	for(node *p = src->n; p; p = p->n) {
		node *q = new node({nullptr, p->r, p->data});
		p->r = q;
		prev->n = q;
		prev = q;		
	}

	vector<node*> saved;

	for(node *p = dst; p; p = p->n) {
		saved.push_back(p->r);
		p->r = p->r->r;		
	}

	int i = 0;
	for(node *p = src; p; p = p->n, i++)
		p->r = saved[i];


	return dst;
}

O(n) time, O(n) space, no maps.

Classic question. Solution and analysis can be googled with 'leetcode-copy-list-with-random-pointer' keyword.
A solution excerpted from the page above using HashMap.

public RandomListNode copyRandomList(RandomListNode head) {
	if (head == null)
		return null;
	HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
	RandomListNode newHead = new RandomListNode(head.label);
 
	RandomListNode p = head;
	RandomListNode q = newHead;
	map.put(head, newHead);
 
	p = p.next;
	while (p != null) {
		RandomListNode temp = new RandomListNode(p.label);
		map.put(p, temp);
		q.next = temp;
		q = temp;
		p = p.next;
	}
 
	p = head;
	q = newHead;
	while (p != null) {
		if (p.random != null)
			q.random = map.get(p.random);
		else
			q.random = null;
 
		p = p.next;
		q = q.next;
	}
 
	return newHead;
}

O(N) solution using a hash map

#include <iostream>
#include <cassert>
#include <functional>
#include <unordered_map>

using namespace std;

struct node {
	int v;
	node* n;
	node* r;
	node(int v, node* n = nullptr, node* r = nullptr) : v(v), n(n), r(r) {}
};

auto clone_random_list = [](const node* list) {
	unordered_map<const node*,node*> cloned;
	function<node*(const node*)> clone_list = [&](const node* n) {
		return n ? cloned[n] = new node(n->v, clone_list(n->n)) : nullptr;
	};
	auto ret = clone_list(list);
	function<void(const node*)> set_rand = [&](const node* n) {
		n ? cloned[n]->r = cloned[n->r], set_rand(n->n), 0 : 0;
	};
	set_rand(list);
	return ret;
};

auto is_same_list = [](const node* a, const node* b) {
	function<bool(const node*, const node*)> impl = [&](const node* a, const node* b) {
		return a && b ? a->v == b->v && a->r->v == b->r->v && impl(a->n, b->n) :
			!a && !b ? true : false;
	};
	return impl(a,b);
};

ostream& operator<<(ostream& os, const node* list) {
	while (list) {
		os << list->v << "->" << list->r->v << " ";
		list = list->n;
	}
	return os;
}

int main() {
	auto n3 = new node(3);
	auto n2 = new node(2, n3);
	auto n1 = new node(1, n2, n3);
	n2->r = n1;
	n3->r = n2;
	cout << n1 << endl;
	
	auto c = clone_random_list(n1);
	cout << c << endl;
	assert(is_same_list(n1, c));
	
	return 0;
}

O(N) time solution with O(1) space.
Say the original list is n1->n2->..., and the result list' is n1'->n2'->....
First, create list' and set:

n1'.next = n1.next;
n1.next = n1';

for all nodes in list'.
Second, iterate on list and set:

n1'.random = n1.random.next;
n1.next = n1'.next;      //restore n1.next
n1'.next = n1.next.next; //adjust n1'.next

for all nodes in list'.
Here is the code:

RandomListNode *copyRandomList(RandomListNode *head) {
    if(!head)
        return NULL;
    RandomListNode * cur = head;
    while(cur){
        RandomListNode * n = new RandomListNode(cur->label);
        n->next = cur->next;
        cur->next = n;
        cur = n->next;
    }
    cur = head;
    RandomListNode * ret = cur->next;
    while(cur){
        RandomListNode * cp = cur->next;
        assert(cp);
        if(cur->random)
            cp->random = cur->random->next;
        cur->next = cp->next;
        if(cp->next)
            cp->next = cp->next->next;
        cur = cur->next;
    }
    return ret;
}

#include <map>
#include <string>

using namespace std;

struct Node
{
	string data;
	Node *next;
	Node *random;
};

Node *copyLinkedList(Node *head)
{
	map<Node *, Node *> m;
	Node *it;
	Node *_head = NULL;
	Node *prev = NULL;
	for (it = head; it; it = it->next)
	{
		Node *n = new Node();
		n->data = string(it->data);
		n->next = NULL;
		n->random = NULL;
		m[it] = n;
	}

	for (it = head; it; it = it->next)
	{
		Node *orig = m[it];
		orig->next = m[it->next];
		orig->random = m[it->random];
	}
	return m[head];
}

Here is C++ version of algorithm running in O(N) with space complexity of O(N)

#include <map>
#include <vector>
using namespace std;

struct node {
	int data;
	node *next;
	node *random;
	node(int d):data(d), next(0), random(0){}
};

node * copy_list(node * r)
{
	map<node*, int> nmap;
	map<node*, int>::iterator found;
	vector<node*> copy;
	int pos = 0;
	node *cur = r;
	while (cur)
	{
		nmap[cur] = pos++;
		copy.push_back(new node(cur->data));
		cur = cur->next;
	}
	cur = r;
	for (int i = 0; i < copy.size(); i++)
	{
		if ((found = nmap.find(cur->random))!= nmap.end())
		{
			copy[i]->random = copy[found->second];
		}
		copy[i]->next = (i <copy.size()-1)? copy[i+1]: 0;
		cur= cur->next;
	}
	return copy[0];	
}

#include <iostream>
#include <map>

typedef struct Node
{
    int         data;
    struct Node *next;
    struct Node *random;
} Node_t;

void copy_list(Node_t *src, Node_t *dst);
void print_list(Node_t *list);

using namespace std;

int main(int argc, char **argv)
{
    // Create List
    Node_t src;

    src.next             = new Node_t;
    src.next->next       = new Node_t;
    src.next->next->next = NULL;

    src.random             = src.next->next;
    src.next->random       = src.next;
    src.next->next->random = &src;

    src.data             = 1;
    src.next->data       = 2;
    src.next->next->data = 3;

    // Print List
    cout << "SRC:" << endl;
    print_list(&src);

    // Copy and Print List
    Node_t dst;
    copy_list(&src, &dst);

    cout << "DST:" << endl;
    print_list(&dst);

    return 0;
}

void copy_list(Node_t *src, Node_t *dst)
{
    if (dst == NULL) return;
    map <Node_t*, Node_t*> nodemap;
    nodemap.insert ( std::pair<Node_t*, Node_t*>(src, dst));
    dst->data = src->data;
    while (src != NULL) {
        if (src->next != NULL) {
            Node_t *tmp = NULL;
            if (nodemap.find(src->next) != nodemap.end()) {
                tmp = nodemap[src->next];
            } else {
                tmp       = new Node_t;
                tmp->data = src->next->data;
                nodemap.insert ( std::pair<Node_t*, Node_t*>(src->next, tmp));
            }
            dst->next = tmp;
        } else {
            dst->next = NULL;
        }
        if (src->random != NULL) {
            Node_t *tmp = NULL;
            if (nodemap.find(src->random) != nodemap.end()) {
                tmp = nodemap[src->random];
            } else {
                tmp       = new Node_t;
                tmp->data = src->random->data;
                nodemap.insert ( std::pair<Node_t*, Node_t*>(src->random, tmp));
            }
            dst->random = tmp;
        } else {
            dst->random = NULL;
        }
        src = src->next;
        dst = dst->next;
    }
}

void print_list(Node_t *list)
{
    /* print data from next */
    Node_t *curnode = list;
    while (curnode != NULL) {
        cout << curnode->data << " -> ";
        curnode = curnode->next;
    }
    cout << "NULL" << endl;

    /* print data from random */
    curnode = list;
    while (curnode != NULL) {
        cout << curnode->data << " : ";
        if (curnode->random == NULL) {
            cout << "NULL";
        } else {
            cout << curnode->random->data;
        }
        cout << endl;
        curnode = curnode->next;
    }
}