将节点插入到不带头指针的排序列表中

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

Answer 2

另一个版本：

基本上复制元素（之后必须进行插入）并更新该副本的下一个指针和数据。头部有特殊情况需要处理。

#include<iostream>
using namespace std;
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* current = this;
        SList* prev = NULL;
        while( current && current->foo < value)
        {
            prev = current;
            current = current->pNext;
        }
        if(prev)
        {
            SList *newNode =  new SList(*prev);
            newNode->foo = value;
            prev->pNext = newNode;
        }
        else
        {
            SList *newNode =  new SList(*current);
            current->foo = value;
            current->pNext = newNode;
        }

    }
protected:
    int         foo;
    SList*      pNext;
};
int main()
{
    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;
}