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
- using System;
- using System.Collections.Generic;
- using System.Diagnostics;
- using System.Linq;
- using System.Text;
- using System.Threading.Tasks;
- using Microsoft.VisualStudio.TestTools.UnitTesting;
- namespace TechQTests.DataStructures
- {
- public class LinkedListWithRandomPointerNode
- {
- public int e;
- public LinkedListWithRandomPointerNode next;
- public LinkedListWithRandomPointerNode random;
- }
- [TestClass]
- public class LinkedListWithRandomPointer
- {
- public LinkedListWithRandomPointerNode DeepCopy()
- {
- if(this._first == null)
- {
- return null;
- }
- LinkedListWithRandomPointerNode i1 = this._first, i2 = null;
- while(i1 != null)
- {
- //cre new node
- i2 = new LinkedListWithRandomPointerNode();
- i2.e = i1.e;
- i2.next = i1.next;
- //insert it after i1
- i1.next = i2;
- i1 = i2.next;
- }
- LinkedListWithRandomPointerNode firstNodeOfCopiedList = this._first.next;
- i1 = this._first; i2 = i1.next;
- while(i2 != null)
- {
- if(i1.random != null)
- {
- i2.random = i1.random.next;
- }
- if(i2.next == null)
- {
- break;
- }
- i1 = i2.next;
- i2 = i1.next;
- }
- i1 = this._first; i2 = i1.next;
- while (i2 != null)
- {
- i1.next = i2.next;
- i1 = i1.next;
- if (i1 != null)
- {
- i2.next = i1.next;
- i2 = i2.next;
- }
- else
- {
- i2.next = null;
- break;
- }
- }
- return firstNodeOfCopiedList;
- }
- [TestMethod]
- public void LinkedListWithRandomPointerTests()
- {
- var n = this.DeepCopy();
- Assert.IsNotNull(n);
- var i1 = this._first; var i2 = n;
- while(i1 != null)
- {
- Assert.IsNotNull(i2);
- Assert.IsTrue(i1.e == i2.e);
- if(i1.random != null)
- {
- Assert.IsNotNull(i2.random);
- Assert.IsTrue(i1.random.e == i2.random.e);
- }
- i1 = i1.next;
- i2 = i2.next;
- }
- }
- LinkedListWithRandomPointerNode _first = null;
- public LinkedListWithRandomPointer()
- {
- this._first = new LinkedListWithRandomPointerNode() { e = 7 };
- this._first.next = new LinkedListWithRandomPointerNode() { e = 14 };
- this._first.next.next = new LinkedListWithRandomPointerNode() { e = 21 };
- this._first.random = this._first.next.next;
- this._first.next.next.random = this._first;
- }
- }
- }
http://www.codeitt.com/linked-lists-in-detail
ReplyDelete