c++ - 将节点插入到没有头指针的排序列表

Question

有人可以改进这个答案吗？我相信 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;
}

Answer 1

首先测试值是否小于 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;
}