2

実行可能ファイルにある2つのリンクリストを取得して、それらを交互の位置にマージしようとしています。元。ListOne 1,2,3 および ListTwo 4,5 新しい ListOne は 1,4,2,5,3 である必要があります。

LinkedList .h ファイル:

class LinkedList
{
private:
struct ListNode
{
    string firstName;
    string lastName;
    long int phoneNumber;
    struct ListNode *next;
};
ListNode *head;

public:
LinkedList()
{
    head = nullptr;
}
~LinkedList();
void appendNode(string f, string l, long int p);
void displayList();
};

LinkedList .cpp ファイル:

LinkedList::~LinkedList()
{
cout << "LinkList destructor" << endl;
}

void LinkedList::appendNode(string f, string l, long int p)
{
    ListNode *newNode;
    ListNode *nodePtr;
    newNode = new ListNode;

    newNode -> firstName = f;
    newNode -> lastName = l;
    newNode -> phoneNumber = p;
    newNode -> next = nullptr;

    if (!head)
        head = newNode;

    else
    {
        nodePtr = head;

        while (nodePtr -> next)
            //while nodePtr is pointing to another node
            nodePtr = nodePtr -> next;
            //move to that node

        nodePtr -> next = newNode;
        //inset the newNode at the end of the linked list
    }
 }

 void LinkedList::displayList()
{
    ListNode *nodePtr;
    nodePtr = head;

    while(nodePtr)
    //while nodePtr is true, meaning there is a node in the list
    {
        cout << nodePtr -> firstName << endl;
        cout << nodePtr -> lastName << endl;
        cout << nodePtr -> phoneNumber << endl;
        nodePtr = nodePtr -> next;
     }
}

実行可能ファイル：

LinkedList ListOne;
LinkedList ListTwo;

ListOne.appendNode("Cate", "Beckem", 7704563454);
ListOne.appendNode("Cabe","Tomas", 7703451523);

ListTwo.appendNode("Mary", "Smith", 4043456543);
ListTwo.appendNode("Mark", "Carter", 4045433454);

私のプログラムは、displayList 関数を含めて完全に実行されます。マージ機能を作成する方法が非常に混乱しています。

4

2 に答える 2

0

マージ関数を作成することは難しくありません。次のように、新しいヘッドを使用して新しいリストを記録し、次にこれら 2 つのリストをトラバースして、ノードをこれら 2 つのリストから新しいリストに順番に移動することができます。

 LinkedList LinkedList::merge(LinkedList b)
{
    // if one list is null, return the other
    if (this->head == nullptr)
        return b;
    if (b.head == nullptr)
        return *this;

    LinkedList newlist;
    ListNode *ap = this->head, *bp = b.head, *p = nullptr;
    // if two pointer is all not null, move node from these to new list in turn
    while (ap != nullptr && bp != nullptr)
    {
        if (newlist.head == nullptr)
        {
            p = newlist.head = ap;
            ap = ap->next;
            p = p->next = bp;
            bp = bp->next;
        }
        else
        {
            p = p->next = ap;
            ap = ap->next;
            p = p->next = bp;
            bp = bp->next;
        }
    }
    // maybe one list is longer, and there is some node left.
    if (ap != nullptr)
        p->next = ap;
    if (bp != nullptr)
        p->next = bp;
    //clear original list
    this->head = b.head = nullptr;
    //if you want to merge list b to the caller list, you can change to
    //this->head = newlist->head and beginning part also need some modification.
    return newlist;
}

元のリストを変更したくない場合は、値をコピーして、新しいリスト用の新しいノードを作成できます。

于 2015-10-28T17:11:23.310 に答える