The original question can be found here.
I implemented method 2:
Please comment about style, unit testing, code complexity, time and memory space and complexity.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication2
{
public class LinkedListArbitraryPointer
{
public ArbNode Root { get; set; }
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;
}
}
public class ArbNode
{
public ArbNode(int index)
{
Index = index;
Next = null;
Arb = null;
}
public ArbNode()
{
Next = null;
Arb = null;
}
public int Index { get; set; }
public ArbNode Next { get; set; }
public ArbNode Arb { get; set; }
}
}
Unit Test
using System;
using System.Linq;
using ConsoleApplication2;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace UnitTests
{
[TestClass]
public class LinkedListArbPointerUnitTest
{
[TestMethod]
public void TestMethod1()
{
LinkedListArbitraryPointer list = new LinkedListArbitraryPointer();
list.Root = new ArbNode(1);
list.Root.Next = new ArbNode(2);
//2->1
list.Root.Next.Arb = list.Root;
list.Root.Next.Next = new ArbNode(3);
//1 -> 3
list.Root.Arb = list.Root.Next.Next;
list.Root.Next.Next.Next = new ArbNode(4);
//4->3
list.Root.Next.Next.Next.Arb = list.Root.Next.Next;
list.Root.Next.Next.Next.Next = new ArbNode(5);
//5->2
list.Root.Next.Next.Next.Next.Arb = list.Root.Next;
//3->5
list.Root.Next.Next.Arb = list.Root.Next.Next.Next.Next;
//var res = list.DeepCopyLinkedListWithAuxArray(list.Root);
var res = list.DeepCopyLinkedList(list.Root);
Assert.AreEqual(1,res.Index);
Assert.AreEqual(3, res.Arb.Index);
}
}
}