gpt4 book ai didi

c++ - 合并两个 LinkedList 而不创建一个新的 LinkedList

转载 作者:塔克拉玛干 更新时间:2023-11-03 07:48:39 24 4
gpt4 key购买 nike

我正在尝试获取可执行文件中的两个链表,并在交替位置将它们合并到一起。前任。 ListOne 1,2,3 和 ListTwo 4,5 新的 ListOne 应该是 1,4,2,5,3。

链表.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();
};

链表 .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 函数。我只是很困惑如何着手制作合并功能。

最佳答案

做一个合并函数并不难。可以只用一个新的head来记录新的list,然后遍历这两个list,依次将这两个list中的结点移动到new list中,如下所示。

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

也许您不想更改原始列表,那么您可以只复制值并为新列表创建新节点。

关于c++ - 合并两个 LinkedList 而不创建一个新的 LinkedList,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33395811/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com