复制链表

Question

我写了一个创建链表副本的方法.
你们能想到比这更好的方法吗？

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;

        }

Answer 1

你可以一次性完成,如下所示:

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;

    }

Answer 2

@Greg,我拿了你的代码,使它甚至更短:)

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;    
}

Do-While构造经常被遗忘,但在这里很合适.
Node.Clone()方法也不错.

+1给Greg这个很好的例子.