c++pointersrecursionlinked-list

Linked-list population via recursion in C++


I want to learn pointers and referencing them.

I will use the following task for example.

I need to populate the linked-list defined below from the given number, where each digit is list's nodes.

struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

The number is 1234.

Therefore the linked list is supposed to look like: 4 -> 3 -> 2-> 1.

I have implemented a function that utilizes recursion to set value and next node.

void nodeFromNumber(int& number, ListNode* node) {
        node->val = number % 10;
        if (number) {
            ListNode newNode {};
            node->next = &newNode ;

            number /= 10;
            nodeFromNumber(number, &newNode );
        }
    }

The problem seems that I cannot set correct pointer from node->next to actual node. I want to learn more on the pointers topic, and it looks like I have a problem understanding why setting pointer to newly created node object's memory address (as far as I understand it has been allocated properly) resolves in error. After walking through list and printing node's value via printList function, I get that first node stores correct value however the rest does not (even though I recursively set newNode->val).

I will provide full program below.

#include <iostream>

using namespace std;

void nodeFromNumber(int& number, ListNode* node) {
    if (number) {
        node->val = number % 10;
        ListNode newNode {};
        node->next = &newNode;
        number /= 10;
        nodeFromNumber(number, &newNode);
    }
}

void printList(ListNode* node) {
    if (node == nullptr) {
        cout << "\nlist ended";    
    } else {
        cout << node->val << endl;
        printList(node->next);
    }
}

int main()
{   
    ListNode node1 {ListNode(3)};
    ListNode node2 {ListNode(3, &node1)};
    ListNode headOdList{ListNode(9, &node2)};

    int number { 1234 };
    ListNode head{};
    nodeFromNumber(number, &head);
    
    cout<<"\nList:\n";
    //case A
    //printList(&head);
    //case B
    printList(&headOdList);
    return 0;
}

Case A: is printing manually created linked list.

example for case A

Case B: is printing the generated linked list, the issue is that it is running in a forever loop, and the second node in the list has random value.

example for case B

Can you help me investigate this?


Solution

  • The main issue is that you make a next member point to the address of a local variable, which will no longer be a valid address once the function returns.

    Create your nodes with new instead.

    Also, since you have a constructor that takes arguments for value and a next pointer, you can reduce your code quite a bit.

    It will also be more elegant if you don't require that the caller of your function must provide the first node. Instead, let the function return the list it has created.

    Suggested code:

    ListNode* nodeFromNumber(int number) {
        return new ListNode(
            number % 10, 
            number / 10 ? nodeFromNumber(number / 10) : nullptr
        );
    }
    

    In your main code you could use it like this:

        ListNode *head = nodeFromNumber(1234);
        printList(head);
    

    Don't forget to delete the nodes if you are in control of the complete program. If you're just writing a function on a code challenge site and it has to return the list, then you'd of course not delete the nodes and leave that for the platform code to clean up.