CODEWITHSUNDEEP
c#linked-list
Learner
Learner

Reputation: 2546

Duplicate a linked list

I wrote a method which creates a copy of linked list.
Can you guys think of any method better than this? 

public static Node Duplicate(Node n)
        {
            Stack<Node> s = new Stack<Node>();

            while (n != null)
            {
                Node n2 = new Node();
                n2.Data = n.Data;
                s.Push(n2);
                n = n.Next;
            }

            Node temp = null;

            while (s.Count > 0)
            {
                Node n3 = s.Pop();
                n3.Next = temp;
                temp = n3;
            }

            return temp;

        }

Upvotes: 5

Views: 9773

Answers (4)

Ultroman the Tacoman
Ultroman the Tacoman

Reputation: 652

I'm sorry if I've missed something, but what's wrong with

LinkedList<MyType> clone = new LinkedList<MyType>(originalLinkedList);

.NET API on LinkedList Constructors

EDIT: Just wanted to emphasize an extremely good point made in the comment below:

"...changing non-value objects on the duplicate changes them on the original too. Meaning you might want to be sure you don't need a deep copy before trying anything on this page."

Upvotes: 2

Yvo
Yvo

Reputation: 19263

@Greg, I took your code and made it even a bit shorter :)

public static Node Duplicate(Node n)
{
     // Handle the degenerate case of an empty list
     if (n == null) return null;

     // Create the head node, keeping it for later return
     Node first = new Node();
     Node current = first;

     do
     {
         // Copy the data of the Node
         current.Data = n.Data;
         current = (current.Next = new Node());
         n = n.Next;
     } while (n != null)

     return first;    
}

The Do-While construct is often forgotten, but fits well here.
A Node.Clone() method would be nice as well.

+1 to Greg for the nice example.

Upvotes: 5

user132748
user132748

Reputation:

Recursive method for small/medium lists.

public static Node Duplicate(Node n)
{
    if (n == null)
        return null;

    return new Node() {
        Data = n.Data,
        Next = Duplicate(n.Next)
    };
}

Upvotes: 2

Greg Hewgill
Greg Hewgill

Reputation: 993105

You can do it in one pass, something like this:

public static Node Duplicate(Node n)
    {
        // handle the degenerate case of an empty list
        if (n == null) {
            return null;
        }

        // create the head node, keeping it for later return
        Node first = new Node();
        first.Data = n.Data;

        // the 'temp' pointer points to the current "last" node in the new list
        Node temp = first;

        n = n.Next;
        while (n != null)
        {
            Node n2 = new Node();
            n2.Data = n.Data;
            // modify the Next pointer of the last node to point to the new last node
            temp.Next = n2;
            temp = n2;
            n = n.Next;
        }

        return first;

    }

Upvotes: 11

Related Questions