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

Question

有人可以改进这个答案吗？我相信 AddNode 函数可以非常小。将节点插入排序链表是一个问题，但有一个警告。你没有头指针。因此，如果节点数据小于头部，则必须将数据交换到class。

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 并插入之前。

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

另一个版本：

基本上复制元素（之后必须完成插入）并更新该副本的下一个指针和数据。 head需要特殊处理

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

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

Insert node to a sorted list without head pointer

c++

algorithm

linked-list

singly-linked-list