Deep copy of linked list with random pointer

Problem

Given a linked list which has random pointer along with next pointer. The random pointer can point to any node in the list. So, how do we create a deep copy of this linked list? and write corresponding code.

Solution

The basic approach is to create copy of the list, and maintain a map of original node and its corresponding copy node (hash table) in first iteration. And in the second iteration update the random pointers of the new list using hash table. The approach takes O(n) time complexity with O(N) additional memory along with copy of linked list.

 

Below is approach 2, with O(1) memory, and by using memory only for creating the copy of linked list. Below is the gist of the basic solution:

 

1. In the first iteration create copy of the linked list, along with that make sure original list nodes points to their corresponding new copy node.

2. In the second iteration, update the random pointer of copied list

3. detach the lists

 

Below is the corresponding code in C# which illustrates the above idea:

Code Snippet

1. using System;
2. using System.Collections.Generic;
3. using System.Diagnostics;
4. using System.Linq;
5. using System.Text;
6. using System.Threading.Tasks;
7. using Microsoft.VisualStudio.TestTools.UnitTesting;
8.  
9. namespace TechQTests.DataStructures
10. {
11.     public class LinkedListWithRandomPointerNode
12.     {
13.         public int e;
14.         public LinkedListWithRandomPointerNode next;
15.         public LinkedListWithRandomPointerNode random;
16.     }
17.     [TestClass]
18.     public class LinkedListWithRandomPointer
19.     {
20.         public LinkedListWithRandomPointerNode DeepCopy()
21.         {
22.             if(this._first == null)
23.             {
24.                 return null;
25.             }
26.             
27.             LinkedListWithRandomPointerNode i1 = this._first, i2 = null;
28.             while(i1 != null)
29.             {
30.                 //cre new node
31.                 i2 = new LinkedListWithRandomPointerNode();
32.                 i2.e = i1.e;
33.                 i2.next = i1.next;
34.                 //insert it after i1
35.                 i1.next = i2;
36.                 i1 = i2.next;
37.             }
38.             LinkedListWithRandomPointerNode firstNodeOfCopiedList = this._first.next;
39.  
40.             i1 = this._first; i2 = i1.next;
41.             while(i2 != null)
42.             {
43.                 if(i1.random != null)
44.                 {
45.                     i2.random = i1.random.next;
46.                 }
47.                 if(i2.next == null)
48.                 {
49.                     break;
50.                 }
51.                 i1 = i2.next;
52.                 i2 = i1.next;
53.             }
54.  
55.             i1 = this._first; i2 = i1.next;
56.             while (i2 != null)
57.             {
58.                 i1.next = i2.next;
59.                 i1 = i1.next;
60.                 if (i1 != null)
61.                 {
62.                     i2.next = i1.next;
63.                     i2 = i2.next;
64.                 }
65.                 else
66.                 {
67.                     i2.next = null;
68.                     break;
69.                 }
70.             }
71.             return firstNodeOfCopiedList;
72.         }
73.         [TestMethod]
74.         public void LinkedListWithRandomPointerTests()
75.         {
76.             var n = this.DeepCopy();
77.             Assert.IsNotNull(n);
78.             var i1 = this._first; var i2 = n;
79.             while(i1 != null)
80.             {
81.                 Assert.IsNotNull(i2);
82.                 Assert.IsTrue(i1.e == i2.e);
83.                 if(i1.random != null)
84.                 {
85.                     Assert.IsNotNull(i2.random);
86.                     Assert.IsTrue(i1.random.e == i2.random.e);
87.                 }
88.                 i1 = i1.next;
89.                 i2 = i2.next;
90.             }
91.         }
92.         LinkedListWithRandomPointerNode _first = null;
93.         public LinkedListWithRandomPointer()
94.         {
95.             this._first = new LinkedListWithRandomPointerNode() { e = 7 };
96.             this._first.next = new LinkedListWithRandomPointerNode() { e = 14 };
97.             this._first.next.next = new LinkedListWithRandomPointerNode() { e = 21 };
98.             this._first.random = this._first.next.next;
99.             this._first.next.next.random = this._first;
100.         }
101.     }
102. }