1

これはインタビューの質問ですが、最善の解決策があるかどうかはわかりません.

質問: (C# または C++ で) 関数を作成して、既に並べ替えられた 2 つのリンクされたリストをマージします。与えられたデータ構造: 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 つのリンク リスト (昇順) を取り込み、それらを (昇順で) 1 つのソート済みリンク リストにマージし、新しいヘッドを返します。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;
        }

いくつかコメントをして、あなたの賢くて良い解決策を教えてください。ありがとうございました！

4

2 に答える 2

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

インタビュアーはおそらくアルゴリズム (あなたのソリューションのようなもの) を探していましたが、これはより現実的でエレガントであり、問​​題解決のスキルと、フレームワークと列挙子の一般的な概念の知識を示していると思います。Java、Python、Ruby (および他の多くのもの) でまったく同じように動作します。ただし、それがC++にどのように変換されるかはわかりません。

于 2013-02-20T23:50:13.033 に答える
0

std::merge の実​​装方法を確認したいかもしれません:
http://www.cplusplus.com/reference/algorithm/merge/

于 2013-02-27T11:03:37.347 に答える