Problem inserting a new node into a sorted linked list

I am attempting to insert a new node into a sorted linked list of integers, but am encountering problems when trying to add to lists that are more than two nodes long. I am using the following code to do this

// Initialise place-holder pointers at first and second nodes
TempPrevious = Head;
TempNext = Head -> Next;

do // Iterate until the right spot is found
{       
    // Does the new node fit between the currently selected nodes?
    if ((NewNode -> Element > TempPrevious -> Element) &&
            (NewNode -> Element < TempNext -> Element))
    {
        NewNode -> Next = TempNext;
        TempPrevious -> Next = NewNode;
        return true;
    }

    // Does the new node fit in further along the list?
    else if (NewNode -> Element > TempNext -> Element)
    {
        // Has the end of the list already been reached?
        if (TempNext -> Next == NULL)
        {
            TempNext -> Next = NewNode;
            return true;
        }

        // Or are there still more nodes to come?
        else if (TempNext -> Next != NULL)
        {
            TempPrevious = TempNext;
            TempNext = TempNext -> Next;
        }
    }
} while (TempNext -> Next != NULL);

I've already accounted for an empty list, a single node list, and a two node list, as well as inserting the new node at the start of a list more then two element long, and all of those parts work fine. I've identified the problem as being the final else if in the provided code as it seems that the pointers TempNext and TempPrevious are not being moved along with each iteration of the do-while loop. I've come to this conclusion after constructing lists containing the following elements and observing the output of the PrintList() function:

Input: 1,2,3,4,5
Output: 1,2,0

Input; 5,4,3,2,1
Output: 1,2,3,4,5

I've looked over my code and ran these tests, but cannot find any fault in the logic. Can anyone else see where I'm going wrong here?

The full list :: Insert() function is

// Insert new element
template <class Type>
bool list<Type> :: Insert (const Type& NewElement)
{
    Node *NewNode;
    Node *TempNext;
    Node *TempPrevious;
    NewNode = new Node;
    NewNode -> Element = NewElement;

    if (Empty()) // If the list is empty
    {
 开发者_运维问答       Head = NewNode;
        return true;
    }

    else if (Head -> Next == NULL) // If there is only a single node in the list
    {
        // If the element is less than or equal to the new one
        if (Head -> Element <= NewNode -> Element)
        {
            Head -> Next = NewNode;
            return true;
        }
        // If the element is greater than the new one
        else if (Head -> Element > NewNode -> Element)
        {
            NewNode -> Next = Head;
            Head = NewNode;
            return true;
        }
    }

    // Multi-node lists - the list has at least two existing nodes

    // Initialise place-holder pointers at first and second nodes
    TempPrevious = Head;
    TempNext = Head -> Next;

    // Does the new node go at the start?
    if (NewNode -> Element < TempPrevious -> Element)
    {
        NewNode -> Next = TempPrevious;
        Head = NewNode;
        return true;
    }

    do // Iterate until the right spot is found
    {       
        // Does the new node fit between the currently selected nodes?
        if ((NewNode -> Element > TempPrevious -> Element) &&
                (NewNode -> Element < TempNext -> Element))
        {
            NewNode -> Next = TempNext;
            TempPrevious -> Next = NewNode;
            return true;
        }

        // Does the new node fit in further along the list?
        else if (NewNode -> Element > TempNext -> Element)
        {
            // Has the end of the list already been reached?
            if (TempNext -> Next == NULL)
            {
                TempNext -> Next = NewNode;
                return true;
            }

            // Or are there still more nodes to come?
            else if (TempNext -> Next != NULL)
            {
                TempPrevious = TempNext;
                TempNext = TempNext -> Next;
            }
        }
    } while (NewNode -> Next != NULL);

    delete TempNext, TempPrevious;
}

You are overcomplicating the issue needlessly. There are several things that aren't quite right in your code:

1. The loop should not be a do ... while -- you want to check if Current == NULL before touching anything (to handle an empty list).
2. Inside the loop you have a test for "am I looking at NewNode's final position?". You don't need any other conditional since if you are not looking at the final position, it's time to continue looping.

You can do it as easy as:

Previous = NULL;
for (Current = Head; Current != NULL; Previous = Current, Current = Current->Next) {
    if (NewNode->Element >= Current->Element) {
        continue;
    }

    // Perform the insertion    
    NewNode->Next = Current;
    if (Current == Head) {
        Head = NewNode;
    }
    else {
        Previous->Next = NewNode;
    }
    return;
}

// We haven't inserted yet after going through all the list
// Previous now points to the last item, or NULL if the list was empty, so:
NewNode->Next = NULL;
if (Previous = NULL) {
    Head = NewNode;
}
else {
    Previous->Next = NewNode;
}
return;

I think the problem is on your while condition, it should be:

while(TmpNext != NULL)

If you already test the empty or the one element list, you can reduce all the other cases to:

TempPrevious = Head;
TempNext = Head->Next;

while(TempNext != NULL)
{
    if (TempNext->Element > NewNode->Element) 
    {
        NewNode->Next = TempNext;
        TempPrevious->Next = NewNode;
        return true;
    }
    TempPrevious = TempNext;
    TempNext = TempNext->Next;
}

// At this point we are sure that we did not inserted the element 
// anywhere in the list so we can safely added to the end
TempPrevious->Next = NewNode;

NewNode -> Next != NULL is always false, so you only get one pass through the loop.

In fact, that loop should continue until the node is inserted. If you end the loop through the condition, it means you haven't inserted the node.

The delete TempNext, TempPrevious at the end is responsible for the 0 in one of your example lists. When you delete through these variables, you destroy the actual elements of the list to which they point.