2
\$\begingroup\$

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);
        }
    }
}
\$\endgroup\$
4
\$\begingroup\$

Var

Use the var keyword when defining local variables where the right hand side of the definition makes the type obvious. This looks cleaner and saves time when it comes to changing types during refactoring.

e.g.

LinkedListArbitraryPointer list = new LinkedListArbitraryPointer();

should be

var list = new LinkedListArbitraryPointer();

You actually do use var at points, but not consistently.

Naming

Avoid using shortened names for your variables, at a glance res is not entirely clear what it refers to, prefer actual or deepCopiedList instead. The same goes for ArbNode.

Definitely don't name your test methods TestMethodX! Find a naming style you like that's concise, detailed and consistent and stick with it.

Comments

Your comments seem to describe what you're doing (which is the job of your code) and not why you are doing it. I often find if there is some chunk of code that needs a comment explaining what it does, it can often be refactored to its own method, or made clearer somehow.

Design

The property 'Root' seems entirely out of place and unused by your code, remove it.

Additionally, I would consider making ArbNode implement IEnumerable so you can replace all your:

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

with a cleaner:

foreach(var node in root)
{
    ...
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.