有人可以改进这个答案吗?我相信 AddNode 函数可以非常小。将节点插入排序链表是一个问题,但有一个警告。你没有头指针。因此,如果节点数据小于头部,则必须将数据交换到类中。
class SList
{
public:
SList(int value = 0,
SList* n = nullptr) :
foo(value), pNext(n)
{
}
void Output()
{
cout << foo;
if (nullptr != pNext)
{
cout << ", ";
pNext->Output();
}
}
void AddNode(int value)
{
SList* head = this;
// Insert to front
if (value < head->foo)
{
int temp = foo;
foo = value;
SList* pNode = new SList(temp);
SList* pNextTmp = this->pNext;
this->pNext = pNode;
pNode->pNext = pNextTmp;
return;
}
// Insert to end
if ((value > head->foo) && nullptr == head->pNext)
{
SList* pNode = new SList(value);
this->pNext = pNode;
return;
}
// Middle case
while (head)
{
if (value > head->foo)
{
if (head->pNext)
{
if (value < head->pNext->foo)
{
SList* pNode = new SList(value);
SList* pNodeTemp = head->pNext;
head->pNext = pNode;
pNode->pNext = pNodeTemp;
return;
}
}
else
{
SList* pNode = new SList(value);
head->pNext = pNode;
}
}
head = head->pNext;
}
}
protected:
int foo;
SList* pNext;
};
void sortedListTest()
{
SList* list = new SList(5);
cout << endl;
list->AddNode(19);
list->AddNode(3);
list->AddNode(8);
list->AddNode(12);
list->AddNode(33);
list->AddNode(9);
list->AddNode(1);
list->AddNode(23);
list->Output();
cout << endl;
}
最佳答案
首先测试值是否小于 head 并创建新的 head。 如果值大于 head 迭代直到下一个元素大于 head 并插入之前。
class SList
{
public:
SList(int value = 0,
SList* n = nullptr) :
foo(value), pNext(n)
{
}
void Output()
{
cout << foo;
if (nullptr != pNext)
{
cout << ", ";
pNext->Output();
}
}
void AddNode(int value)
{
SList* head = this;
// Insert to front
if (value < head->foo)
{
SList* pNode = new SList(foo);
pNode->pNext = this->pNext;
this->pNext = pNode;
foo = value;
return;
}
while ( head->pNext && head->pNext->foo < value )
head = head->pNext;
SList* pNode = new SList(value);
pNode->pNext = head->pNext;
head->pNext = pNode;
}
protected:
int foo;
SList* pNext;
};
void sortedListTest()
{
SList* list = new SList(5);
cout << endl;
list->AddNode(19);
list->AddNode(3);
list->AddNode(8);
list->AddNode(12);
list->AddNode(33);
list->AddNode(9);
list->AddNode(1);
list->AddNode(23);
list->Output();
cout << endl;
}
关于c++ - 将节点插入到没有头指针的排序列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34250144/