Running until a certain value linked list

user_17270790 0
Viewed 71

I want to sum the nodes until 0 is reached and update the original linked list with the new values.

Note: it skips 0 until it reaches a number to calc sum or the end of the linked list.

Definition of node:

struct Node {
int data;
Node* next;
};

void updateLinkedList(Node* head)
{
Node* currentNode = head;

int temp = 0;
int sum = 0;


while (currentNode != NULL)
{
    temp = currentNode->data;

    while(temp != 0)
    {
        sum = sum + currentNode->data;
        currentNode = currentNode->next;
    }
}
}

I'm attempting to do the next thing:

User input linked list:

1 2 0 5 3 0 4

Updated Linked List:

3 8 4
function-definition singly-linked-list linked-list struct c++
3 Answers

The function can be implemented for example the following way

void updateLinkedList( Node * &head )
{
    for ( Node **current = &head; *current != nullptr; )
    {
        if ( ( *current )->data == 0 )
        {
            Node *tmp = *current;
            *current = ( *current )->next;
            delete tmp;
        }
        else
        {
            while ( ( *current )->next != NULL && ( *current )->next->data != 0 )
            {
                ( *current )->data += ( *current )->next->data;
                Node *tmp = ( *current )->next;
                ( *current )->next = ( *current )->next->next;
                delete tmp;
            }

            current = &( *current )->next;
        }
    }
}

Here is a demonstration program.

#include <iostream>

struct Node
{
    int data;
    Node *next;
};

void clear( Node * &head )
{
    while (head != nullptr)
    {
        Node *tmp = head;
        head = head->next;
        delete tmp;
    }
}

void assign( Node * &head, const int a[], size_t n )
{
    clear( head );

    for (Node **current = &head; n--; current = &( *current )->next)
    {
        *current = new Node{ *a++, nullptr };
    }
}

std::ostream &display( const Node * const &head, std::ostream &os = std::cout )
{
    for (const Node *current = head; current != nullptr; current = current->next)
    {
        os << current->data << " -> ";
    }

    return os << "null";
}

void updateLinkedList( Node * &head )
{
    for (Node **current = &head; *current != nullptr; )
    {
        if (( *current )->data == 0)
        {
            Node *tmp = *current;
            *current = ( *current )->next;
            delete tmp;
        }
        else
        {
            while (( *current )->next != NULL && ( *current )->next->data != 0)
            {
                ( *current )->data += ( *current )->next->data;
                Node *tmp = ( *current )->next;
                ( *current )->next = ( *current )->next->next;
                delete tmp;
            }

            current = &( *current )->next;
        }
    }
}

int main()
{
    Node *head = nullptr;

    const int a[] = { 0, 0, 1, 2, 0, 5, 3, 0, 4 };
    const size_t N = sizeof( a ) / sizeof( *a );

    assign( head, a, N );

    display( head ) << '\n';

    updateLinkedList( head );

    display( head ) << '\n';

    clear( head );
}

The program output is

0 -> 0 -> 1 -> 2 -> 0 -> 5 -> 3 -> 0 -> 4 -> null
3 -> 8 -> 4 -> null
user_28772410

In modern C++ you rarely want to deal directly with memory allocation. You'll usually use classes from the standard library or another library. That's because it's easy to forget something and cause your entire program to crash or create memory leaks.

It's important to be familiar with memory allocation and to know how to implement a linked list manually. That's handled by Vlad's answer.

I wanted to add: in the future, you'll probably want to use higher level functionality. This is how I'd write your function if you were using std::forward_list, one of the standard containers.

void updateLinkedList(std::forward_list<int>& list)
{
    auto lastIt = list.before_begin();

    for (auto it = std::begin(list); it != std::end(list);)
    {
        if (*it)
        {
            lastIt = it++;
            int sum = *lastIt;

            while (it != std::end(list) && *it)
            {
                sum += *it;
                it++;
                list.erase_after(lastIt);
            }

            *lastIt = sum;
        }
        else
        {
            it++;
            list.erase_after(lastIt);
        }
    }
}

EDIT: for testing:

#include <forward_list>
#include <iostream>

void printList(const std::forward_list<int>& list)
{
    std::cout << "{ ";
    for (auto& i : list)
    {
        std::cout << i << ", ";
    }
    std::cout << "}\n";
}

void updateLinkedList(std::forward_list<int>& list)
{
    auto lastIt = list.before_begin();

    for (auto it = std::begin(list); it != std::end(list);)
    {
        if (*it)
        {
            lastIt = it++;
            int sum = *lastIt;

            while (it != std::end(list) && *it)
            {
                sum += *it;
                it++;
                list.erase_after(lastIt);
            }

            *lastIt = sum;
        }
        else
        {
            it++;
            list.erase_after(lastIt);
        }
    }
}

int main() {
    std::forward_list list{
        0, 0, 1, 2, 0, 5, 3, 0, 0, 4, 0, 0, 0,
    };

    printList(list);
    updateLinkedList(list);
    printList(list);
}

On compiler explorer.

user_41842030

In your function, the inner while loop seems to be an infinite loop if the initial value of temp!=0, since temp isn't being updated anywhere inside the loop. The node pointed to by currentNode gets updated but temp refers to the value contained by the node initially pointed to by currentNode before entering the inner while loop.

user_175084190
Related