Reverse linked list in a function, that also has to work with a linked list

user_18701364 0
Viewed 42

I had to create a function, that deletes nodes that have a greater element to the right. I achieved this by creating 2 functions: 1st function reverses a list 2nd function that deletes nodes, that have a lesser value than the current node.

In order for this to work I reverse a list, call the 2nd function and reverse the list back. My problem is: How can I combine these 2 functions together, so I can, for example call the reverse function inside the lesVal function without needing to call it separately.

void reverse(Elem** listHead){
    Elem* next;
    Elem* curr = *listHead;
    Elem* temp = NULL;
    while (curr != NULL){
        next = curr->next;
        curr->next = temp;
        temp = curr;
        curr = next;
    }
    *listHead = temp;
}


void lesVal(Elem* listHead){
    Elem* temp;
    Elem* curr = listHead;
    Elem* compare = listHead;
    while (curr != NULL && curr->next != NULL){
        if (curr->next->number < compare->number){
            temp = curr->next;
            curr->next = temp->next;
            delete temp;
        }
        else{
            curr = curr->next;
            compare = curr;
        }

    }
}
reverse(&first);
lesVal(first);
reverse(&first);
function-definition singly-linked-list delete-operator linked-list c++
1 Answers

I had to create a function, that deletes nodes that have a greater element to the right. I achieved this by creating 2 functions: 1st function reverses a list 2nd function that deletes nodes, that have a lesser value than the current node.

It is an inefficient approach. Your task is to delete nodes that have a greater element to the right. So you need to write one function that performs the deletion and nothing more,

The function is very simple.

void lesVal( Elem **listHead )
{
    while ( *listHead && ( *listHead )->next ) 
    {
        if ( ( *listHead )->number < ( *listHead )->next->number )
        {
            Elem *tmp = *listHead;
            *listHead = ( *listHead )->next;
            delete tmp;
        }
        else
        {
            listHead = &( *listHead )->next;
        }
    }
}

If to include header <utility> then the function can have even less lines. For example

#include <utility>

//...

void lesVal( Elem **listHead )
{
    while ( *listHead && ( *listHead )->next ) 
    {
        if ( ( *listHead )->number < ( *listHead )->next->number )
        {
            delete std::exchange( *listHead, ( *listHead )->next );  
        }
        else
        {
            listHead = &( *listHead )->next;
        }
    }
}

Though as it is a C++ code then it is better to pass the pointer to the head node by reference. In this case the function will look like

void lesVal( Elem * &listHead )
{
    for ( Elem **current = &listHead; *current  && ( *current )->next; ) 
    {
        if ( ( *current )->number < ( *current )->next->number )
        {
            delete std::exchange( *current, ( *current )->next );  
        }
        else
        {
            current = &( *current )->next;
        }
    }
}

If you want to repeat deletions of nodes until the list will be sorted in the descending order then a straightforward approach can look the following way.

void lesVal( Elem * &listHead )
{
    bool removed = true;

    while ( removed )
    {
        removed = false;
        for ( Elem **current = &listHead; *current  && ( *current )->next; ) 
        {
            if ( ( *current )->number < ( *current )->next->number )
            {
                removed = true;
                delete std::exchange( *current, ( *current )->next );  
            }
            else
            {
                current = &( *current )->next;
            }
        }
    }
}
user_28772410
Related