CareerCup

We need to run three iterations over a linked list, which takes O(n) time.

input: a b c NULL
output: a' b' c' NULL

1) Create nodes for an output and adjust "next" pointers for the input and the output in such a way to build a a' b b' c c' NULL

2) Adjust "random" pointers for the output by using the random and next pointers of the input list. For example, b'->random = b->random->next

3) Adjust next pointers for the input and output lists. For example, temp = (b'->next)?b'->next->next:NULL; b->next = b'->next; b'->next = temp;

L: a b c d ...

L': a A b B c C ...

A→random = a→random→next

Split L' into two list

There are ways that involve trickery, which you want to avoid in interview settings. It might be fun to try these funky ways when you are home drinking coffee and chilling.

A good linear way is to use a map.

1) Go through your linked list, and for each node v, create a new node u, such that u->data = v->data. Now store (v,u) in your map. {Note, doesn't matter where you set the u->next, just leave the new nodes dangling in the air}

2) Now go through your original linked list again, and visit every v.

Now do 3 lookups in the map for every in your original linked list....
Look up v to get u.
Look up v->next to get whatever, call it x
Look up v->random to get whatever, call it y

Now set u->next = x, u->random=y.

A simple implementation using a map from old nodes to the corresponding new. First clone the list while setting the next pointers. Then, iterate again and adjust the random pointers using the map created in the previous step.

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

import util.RLNode;


public class CloneRandomLinkList {

	public static RLNode cloneList(RLNode head){
		if(head == null) return null;

		Map<RLNode, RLNode> oldToNew = new HashMap<>();


		RLNode newHead = new RLNode(head.value());
		oldToNew.put(head, newHead);
		RLNode cur = head;
		RLNode curCopy = newHead;
		while(cur.next != null){
			curCopy.next = new RLNode(cur.next.value());
			oldToNew.put(cur.next,curCopy.next);

			cur = cur.next;
			curCopy = curCopy.next;

		}

		cur = head;
		curCopy = newHead;
		while(cur != null){
			curCopy.random = oldToNew.get(cur.random);
			cur = cur.next;
			curCopy = curCopy.next;
		}

		return newHead;

	}
	
	public static void main(String[] args) {
		int N = 10;
		RLNode [] nodes = new RLNode[N];
		
		RLNode head = new RLNode(0);
		nodes[0] = head;
		
		RLNode prev = head;
		for (int i = 1; i < N; i++) {
			nodes[i] = prev.next = new RLNode(i);
			prev = prev.next;
		}
		
		RLNode.printList(head);
		
		Random rand = new Random(2);
		for (int i = 0; i < N; i++) {
			nodes[i].random = nodes[rand.nextInt(N)];
		}
		RLNode.printList(head);
		
		RLNode copy = cloneList(head);
		System.out.println("Copy:");
		RLNode.printList(copy);
		
		
	}
	


}

class RLNode {
	
	public RLNode(double val, RLNode n){
		data = val;
		next = n;	
	}

	public RLNode(double val){
		this(val, null);
	}


	public Double value(){ return data; }
	
	public double data;
	public RLNode next;
	public RLNode random;
	
	@Override
	public String toString() {
		return "["+data+(random==null?"":"/"+random.value())+"]";
	}

	public static void printList(RLNode head) {
		RLNode cur = head;
		StringBuilder sb = new StringBuilder();
		while(cur != null ){
			sb.append(cur.toString()).append("->");
			cur = cur.next;
		}		
		sb.append("||"); 
		System.out.println(sb.toString());
		
	}
	
}

can we use extra data structure, like map something, it makes big difference in terms of difficulty.

struct list* copyll(struct *list)
{
	struct list *head, *fptr, *sptr, *ffptr, temp;
	
	while(list)
	{
		temp = (struct list *) malloc(struct list);
		temp->random = NULL;
		temp->next = NULL;
		if(!head)
		{
	 		head = sptr = temp;	
		}else
		{
			sptr->next = temp;
			sptr = temp;
		}
		sptr->data = list->data;
		list = list->next;	
	}
	
	fptr = ffptr = head; /* new list */
	temp = list; /* old list */
	
	while(temp)
	{
		sptr = temp;
		fptr = head;
		while (sptr!= NULL && temp->random->data != sptr->data)
		{
			sptr = sptr->next;
			fptr = fptr->next;
		}
		ffptr->random = fptr;
		ffptr = ffptr->next;
		temp = temp->next;
	}
	return head;
}

/* Complexity is high when setting random pointers */

Clone linked list having random references between nodes
Random references don't loop nodes. This solution is in JavaScript for Demo Purposes only. It is unacceptable JavaScript structure since it creates loops between objects in memory and JavaScript is not capable to GC it.

var d = { value: "D", next: null, random: null };
var c = { value: "C", next: d, random: null };
var f = { value: "F", next: c, random: null };
var b = { value: "B", next: f, random: null };
var e = { value: "E", next: b, random: null };
var a = { value: "A", next: e, random: null };

a.random = c;
c.random = e;
b.random = d;
e.random = d;
f.random = a;
d.random = f;

function cloneLL(currentItem) {
	var result = null;
	var prevItem = null;
	var itemsHash = {};
	var itemsReferences = {};
	while (currentItem != null) {
		var newItem = { value: currentItem.value, next: null, random: null, newItem: true };

		if (prevItem != null) {
			prevItem.next = newItem;
		}

		itemsHash[newItem.value] = newItem;

		if (itemsHash.hasOwnProperty(currentItem.random.value)) {
			newItem.random = itemsHash[currentItem.random.value];
		} else {
			if (!itemsReferences.hasOwnProperty(currentItem.random.value)) {
				itemsReferences[currentItem.random.value] = [currentItem.value];
			} else {
				itemsReferences[currentItem.random.value].push(currentItem.value);
			}
		}

		if (itemsReferences.hasOwnProperty(newItem.value)) {
			var items = itemsReferences[newItem.value];

			for (var index = 0; index < items.length; index += 1) {
				var reference = items[index];

				itemsHash[reference].random = newItem;
			}
		}

		if (result == null) {
			result = newItem;
		}

		prevItem = newItem;
		currentItem = currentItem.next;
		
	}

	return result;
}

var newLL = cloneLL(a);

struct Node {
    Node* next;
    Node* random;
    int value;
};

Node* copy(Node* head) {
    if (!head) return NULL;

    // copy the list
    Node* cur = head;
    while (cur) {
        Node* node = new Node();
        node->value = cur->value;
        node->random = NULL;
        node->next = cur->next;
        cur->next = node;
        cur = node->next;
    }

    // update random correctly
    cur = head;
    while (cur) {
        cur->next->random = cur->random ? cur->random->next : NULL;
        cur = cur->next->next;
    }

    // split list    
    Node* newhead = head->next;
    Node* newcur = newhead;
    cur = head;
    while (cur) {
        cur->next = newcur->next;
        cur = cur->next;
        newcur->next = cur ? cur->next : NULL;
        newcur = newcur->next;
    }
    
    return newhead;
}

This question was asked to me for a Google SRE Phone screen Interview 2 years back. The solution uses 1 hashmap and 3 passes.

Create a copy of the link list (without considering the random pointer) while you do that fill the hashmap with Key = Original Node Value = New Node

Second pass go over both the linked (new and original) again
then go over hashmap and use the value to fill up the random pointer position in the new list.

Node* CopyLinkedList(Node* head) {
Node* n = head;
// First pass, insert a copy next to the code.
while (n) {
Node* n1 = new Node();
n1->data = n->data;
n1->next = n->next;
n->next = n1;
n = n->next->next;
}
// Second pass, set random pointer.
n = head;
while (n) {
n->next->random = n->random->next;
n = n->next->next;
}
// Third pass, detach two lists.
n = head;
Node* head1 = n->next;
while (n) {
Node* temp = n->next->next;
n->next->next = temp ? temp->next : nullptr;
n->next = temp;
n = temp;
}
return head1;
}

public ArbNode DeepCopyLinkedList(ArbNode root)
{
if (root == null)
{
return null;
}

//1) Create the copy of node 1 and insert it between node 1 & node 2 in original Linked List, create the copy of 2 and insert it between 2 & 3..
//Continue in this fashion, add the copy of N afte the Nth node
ArbNode temp = root;
while (temp != null)
{
ArbNode swap = temp.Next;
temp.Next = new ArbNode(temp.Index);
temp.Next.Next = swap;
temp = temp.Next.Next;
}

// 2) Now copy the arbitrary link in this fashion
// original->next->arbitrary = original->arbitrary->next; /*TRAVERSE TWO NODES*/

temp = root;
while (temp != null)
{
temp.Next.Arb = temp.Arb.Next;
temp = temp.Next.Next;
}

//3) Now restore the original and copy linked lists in this fashion in a single loop.
temp = root;
ArbNode current = root.Next;
ArbNode storeList = root.Next;
while (temp != null)
{
temp.Next = temp.Next.Next;
if (current.Next != null)
{
current.Next = current.Next.Next;
}
temp = temp.Next;
current = current.Next;
}

return storeList;
}