複製一個鏈表

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

用於小型/中型列出的遞歸方法。

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

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

Answer 3

@格雷格，我把你的代碼，並使它變得有點短:)

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

該做的，雖然結構往往被遺忘，但非常適合這裏。
Node.Clone（）方法也不錯。

+1給格雷格的好例子。