Confusion in different ways of creating nodes in C++?

user_13251545 0
Viewed 101

I was trying to solve merge two sorted linked list problem from leetcode.

I solved the problem but here's something which I'm not understanding, When I try to create nodes and their pointers using 'new' keyword(which stores the nodes in heap memory) it works, but when I change it to first creating node and then creating a pointer to it then it shows "stack-use-after-scope".

Here's the commented code-

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) {}
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==NULL) return l2;
        if(l2==NULL) return l1;
        
        // ListNode *res = new ListNode() works but this doesn't
        ListNode dummy(0);
        ListNode *res = &dummy;
        
        // just comparing the initial 2 values of both linked list-
        if(l1->val<l2->val){
            res->val=l1->val;
            l1=l1->next;
        }else{
            res->val=l2->val;
            l2=l2->next;
        }

        // head variable is to store the head of resultant linked list-
        ListNode *head;
        head=res;
        
        // while both list contains elements-
        while(l1!=NULL && l2!=NULL){
            // ListNode *x = new ListNode() works but this doesn't
            ListNode y(0);
            ListNode *x = &y;
            if(l1->val<l2->val){
                x->val=l1->val; 
                l1=l1->next;
            }else{
                x->val=l2->val;
                l2=l2->next;
            }
            res->next = x;
            res = x;
        }
        
        // if list1 has some elements left-
        while(l1!=NULL){
            // ListNode *x = new ListNode() works but this doesn't
            ListNode y(0);
            ListNode *x = &y;
            x->val=l1->val;
            res->next=x;
            res=x;
            l1=l1->next;
        }

        // if list2 has some elements left-
        while(l2!=NULL){
            // ListNode *x = new ListNode() works but this doesn't
            ListNode y(0);
            ListNode *x = &y;
            x->val=l2->val;
            res->next=x;
            res=x;
            l2=l2->next;
        }
        return head;
    }

Can anyone please help?

c++14 c++17 data-structures linked-list c++
2 Answers

Maybe we'd simplify our statements here.

This'll simply pass:

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
const static struct Solution {
    ListNode* mergeTwoLists(
        ListNode* l1,
        ListNode* l2
    ) {
        ListNode sentinel(0);
        ListNode* head = &sentinel;

        while (l1 && l2) {
            if (l1->val < l2->val) {
                head->next = l1;
                l1 = l1->next;

            } else {
                head->next = l2;
                l2 = l2->next;
            }

            head = head->next;
        }

        head->next = l1 ? l1 : l2;
        return sentinel.next;
    }
};

Since we are using a Sentinel Node, we'd eventually return sentinel.next instead of head.

References

  • For additional details, please see the Discussion Board where you can find plenty of well-explained accepted solutions with a variety of languages including low-complexity algorithms and asymptotic runtime/memory analysis1, 2.
user_65533280

The automatic variable dummy is both the cause of your problem, and simultaneously unnecessary.

Merging two lists simply means crafting a node chain from the other nodes, which are already allocated. Since you have no list "wrapper" (i.e. an object that contains both the node chain and other information such as a count, tail pointer, etc), this simply because an exercise of merging the node chains, which requires a single target pointer and an enumerating pointer-to-pointer to cinch up the results.

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
{
    ListNode *res = nullptr;
    ListNode **pp = &res;

    while (l1 && l2)
    {
        if (l1->val < l2->val)
        {
            *pp = l1;
            pp = &l1->next;
            l1 = l1->next;
        }
        else
        {
            *pp = l2;
            pp = &l2->next;
            l2 = l2->next;
        }
    }

    // one of the lists will have elements left. chain that
    //  to the list-end and we're done.
    *pp = l1 ? l1 : l2;

    return res;
}

That's it. One thing worth mentioning. This will truly merge the two input lists. Meaning: the caller's l1 and l2 pointers passed as arguments aren't really worth anything anymore, and should be summarily discarded. The nodes of the original two lists are now joined into a single list that is returned as a result of this function. If you want to make a copy of the input lists whilst creating your merge, a different strategy is warranted, but I see no evidence of that requirement in your stated problem.

user_13229720
Related