如何合併兩個排序後的鏈接列表？

Question

這是一個面試問題，但如果有最好的解決方案，我不會。

問題：編寫一個函數（用C＃或C++）合併兩個已排序的鏈接列表。給定的數據結構： C++：

class Node 
{ 
public: 
int data; 
Node* next; 
}; 

C＃：

class Node 
{ 
public int data; 
public Node next; 
}; 

實現函數： 在C++：

Node* Merge (Node* head1, Node* head2) 
{ 
… 
} 

在C＃：

Node Merge (Node head1, Node head2) 
{ 
… 
} 

它需要兩個人準備好的已排序的鏈接列表（以上升的順序），並且應該將它們合併成單個排序的鏈接列表（以順序排列的順序）並返回新的頭部。 2個列表可能具有相同數據的節點（int值）。我們預計結果列表中沒有相同的數據。

我的解決辦法：

Node Merge(Node head1, Node head2) 
     { 
      Node merged = head1; 
      // Both lists are empty 
      if (head1 == null && head2 == null) 
      { 
       return null; 
      } 
      // List 1 is empty 
      else if (head1 == null && head2 != null) 
      { 
       return head2; 
      } 
      // List 2 is empty 
      else if (head2 == null && head1 != null) 
      { 
       return head1; 
      } 
      // Both lists are not empty 
      else 
      { 
       Node cursor1 = head1; 
       Node cursor2 = head2; 

       if (cursor1.next.data > cursor2.data) 
       { 
        Node temp = cursor1; 
        cursor1 = cursor2; 
        cursor2 = temp; 
       } 

// Add all elements from list 2 to list 1 
       while (cursor1.next != null && cursor2 != null) 
       { 
        if (cursor1.next.data < cursor2.data) 
        { 
         cursor1 = cursor1.next; 
        } 
        else 
        { 
         Node temp1 = cursor1.next; 
         Node temp2 = cursor2.next; 
         cursor1.next = cursor2; 
         cursor2.next = temp1; 

         cursor1 = cursor1.next; 
         cursor2 = temp2; 
        } 
       } 

       if (cursor1.next == null) 
       { 
        cursor1.next = cursor2; 
       } 
      } 

      // Remove duplicates 
      head1 = merged; 
      while (head1.next != null) 
      { 
       if (head1.data < head1.next.data) 
       { 
        head1 = head1.next; 
       } 
       else if (head1.data == head1.next.data) 
       { 
        head1.next = head1.next.next; 
       } 
      } 
      return merged; 
     } 

請給一些意見，讓我知道你的聰明和良好的解決方案。謝謝！

Answer 1

確定我被允許使用與C＃一起使用的框架之後，這就是我所要做的。

鑑於此鏈表類（和你的一樣，但使用性質）

class Node 
{ 
    public int Data { get; set; } 
    public Node Next { get; set; } 
} 

爲列表創建IEnumerator

class NodeEnumerator : IEnumerator<int> 
{ 
    private Node _current_node; 

    public NodeEnumerator(Node first) { 
     _current_node = new Node { Data = 0, Next = first }; 
    } 

    public int Current { 
     get { return _current_node.Data; } 
    } 

    object IEnumerator.Current { 
     get { return Current; } 
    } 

    public bool MoveNext() { 
     if (_current_node == null) { 
      return false; 
     } 
     _current_node = _current_node.Next; 
     return _current_node != null; 
    } 

    public void Reset() { 
     throw new NotSupportedException(); 
    } 

    public void Dispose() { 

    } 
} 

創建相應的IEnumerable

class EnumerableNode : IEnumerable<int> 
{ 
    private Node _first; 
    public EnumerableNode(Node first) { 
     _first = first; 
    } 
    public IEnumerator<int> GetEnumerator() { 
     return new NodeEnumerator(_first); 
    } 

    IEnumerator IEnumerable.GetEnumerator() { 
     return GetEnumerator(); 
    } 
} 

然後使用我可以用這個功能來交換這些令人敬畏的功能舉手之勞，即Concat和Distinct

class Program 
{ 
    static void Main(string[] args) { 
     var list1 = new EnumerableNode(
      new Node { Data = 1, Next = 
      new Node { Data = 2, Next = 
      new Node { Data = 3, Next = null }}}); 
     var list2 = new EnumerableNode(
      new Node { Data = 2, Next = 
      new Node { Data = 3, Next = 
      new Node { Data = 4, Next = null }}}); 
     var merged = list1.Concat(list2).Distinct(); 
     Console.WriteLine(String.Join(",", list1)); 
     Console.WriteLine(String.Join(",", list2)); 
     Console.WriteLine(String.Join(",", merged)); 
     Console.ReadLine(); 
    } 
} 

輸出

1,2,3 
2,3,4 
1,2,3,4 

面試官很可能是在尋找Algorithmics的（如您的解決方案），但我認爲這是更逼真，更優雅，而且還顯示解決問題的技巧，以及關於統計員的框架和一般概念的知識。它在Java，Python和Ruby（以及其他許多我確信）中的工作原理完全相同。我不知道它將如何轉換爲C++。

Answer 2

你可能想看看的std ::合併是如何實現的：
http://www.cplusplus.com/reference/algorithm/merge/