0

I have a code like below :

#include <iostream>

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

void print(ListNode *head) {
    ListNode *l = head;
    while (l)
    {
        std::cout << "val is " << l->val << std::endl;
        l = l->next;
    }
}

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
{
    int sum = 0, quo = 0, rem = 0;
    ListNode *head = (ListNode *)malloc(sizeof(ListNode));
    ListNode *curr, *prev = nullptr;
    while (l1 || l2)
    {
        // Calculate value
        sum = (l1->val + l2->val + quo);
        quo = sum / 10;
        rem = sum - quo * 10;

        // Add node
        if(prev == nullptr) {
            curr = head;
        } else {
            curr = (ListNode *)malloc(sizeof(ListNode));
            prev->next = curr;
        }
        curr->val = rem;
        prev = curr;
        l1 = l1->next;
        l2 = l2->next;
    }
    return head;
}



int main() {
    ListNode *node1_1 = (ListNode *)malloc(sizeof(ListNode));
    ListNode *node1_2 = (ListNode *)malloc(sizeof(ListNode));
    ListNode *node1_3 = (ListNode *)malloc(sizeof(ListNode));
    node1_1->val = 2;
    node1_2->val = 4;
    node1_3->val = 3;
    node1_1->next = node1_2;
    node1_2->next = node1_3;

    ListNode *node2_1 = (ListNode *)malloc(sizeof(ListNode));
    ListNode *node2_2 = (ListNode *)malloc(sizeof(ListNode));
    ListNode *node2_3 = (ListNode *)malloc(sizeof(ListNode));
    node2_1->val = 5;
    node2_2->val = 6;
    node2_3->val = 4;
    node2_1->next = node2_2;
    node2_2->next = node2_3;

    free(node1_1);
    free(node1_2);
    free(node1_3);
    free(node2_1);
    free(node2_2);
    free(node2_3);

    print(addTwoNumbers(node1_1, node2_1));
}

The problem is, when I am trying to run this code on vscode, I keep getting error :

/bin/sh: line 1: 96278 Segmentation fault: 11 "/Users/cpp/"leet_add_two_nums

I suspect that this issue is related to malloc, but cannot find a clue.

I have tried to free after malloc, but that was not the problem.

I am very new to C++, can anyone help?

Also, I would really appreciate if anyone tell me how I could improve my code!

Thanks so much in advance!

7
  • 2
    🔎🐞Did run your code in a debugger to see where that error occurs, then run it again with a breakpoint near that failure so you can step carefully ahead and watch what happens leading up to that point? Commented May 13, 2020 at 19:46
  • 3
    You're including iostream, so I'm assuming this really is C++ and not C...in which case, don't use raw malloc and free!! At least use new and delete, but even better would be switching to smart pointers. Commented May 13, 2020 at 19:47
  • @jamesdean It is a good idea to call these functions print(addTwoNumbers(node1_1, node2_1)); after deleting all nodes.:) Commented May 13, 2020 at 19:52
  • I'm not 100% sold on smart pointers with linked lists. I do some big lists. Commented May 13, 2020 at 19:53
  • @Vlad I'm guessing you mean "It is NOT a good idea [...]"? Commented May 13, 2020 at 19:59

3 Answers 3

1
while (l1 || l2)

This means "while either l1 is not nullptr OR l2 is not nullptr, keep looping!

You want an AND there:

while(l1 && l2)

Furthermore, you free all the nodes of your list before you call addTwoNumbers! Move your addTwoNumbers call up to before all the free's.

See it run here: https://ideone.com/f4kBIh

Sign up to request clarification or add additional context in comments.

Comments

0

The problem can be fixed easily by replacing malloc with 'new'

Use of 'new' gives these benefits:

  • Make the program resilient to common issues with malloc.
  • Remove the need for the explicit calls to 'free'.

Here is the working code with malloc replaced by new:

#include <iostream>

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

void print(ListNode *head) {
    ListNode *l = head;
    while (l) {
        std::cout << "val is " << l->val << std::endl;
        l = l->next;
    }
}

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
    int sum = 0, quo = 0, rem = 0;
    ListNode *head = new ListNode[(sizeof(ListNode))];
    ListNode *curr, *prev = nullptr;
    while (l1 || l2) {
        // Calculate value
        sum = (l1->val + l2->val + quo);
        quo = sum / 10;
        rem = sum - quo * 10;

        // Add node
        if(prev == nullptr) {
            curr = head;
        } else {
            curr = new ListNode[(sizeof(ListNode))];
            prev->next = curr;
        }
        curr->val = rem;
        prev = curr;
        l1 = l1->next;
        l2 = l2->next;
    }
    return head;
}

int main() {
    ListNode *node1_1 = new ListNode[(sizeof(ListNode))];
    ListNode *node1_2 =  new ListNode[(sizeof(ListNode))];
    ListNode *node1_3 =  new ListNode[(sizeof(ListNode))];
    node1_1->val = 2;
    node1_2->val = 4;
    node1_3->val = 3;
    node1_1->next = node1_2;
    node1_2->next = node1_3;

    ListNode *node2_1 = new ListNode[(sizeof(ListNode))];
    ListNode *node2_2 = new ListNode[(sizeof(ListNode))];
    ListNode *node2_3 = new ListNode[(sizeof(ListNode))];
    node2_1->val = 5;
    node2_2->val = 6;
    node2_3->val = 4;
    node2_1->next = node2_2;
    node2_2->next = node2_3;

    print(addTwoNumbers(node1_1, node2_1));
}

Output:

val is 7
val is 0
val is 8

2 Comments

Thank you so much! Is it okay to say that new is always preferred over malloc in c++?
Yes. Definitely. It is always better to use new instead of malloc in all applications. 'new' is the convenient and defect-free way to initialize objects. 'malloc' is a legacy feature from C language and hence may be used for legacy support only.
0

Ok so some comments about this code

Constructors are great in classes, but if you use C malloc then the constructor is not executed.

Use new and delete for your classes/structs e.g. ListNode, that way next will actually be null as you specify in your constructor, otherwise it will be uninitialized

Your while loop

while (l1 || l2) 

will continue until both are null, but if one of them happens to turn to null you will derereference it since the other is potentially not null:

    l1 = l1->next;
    l2 = l2->next;

(btw use better variable names, there is no advantage using short, cryptic variable names)

In you main function - you have already freed the memory of node1_1 and node1_2 but still use it in your function call print(addTwoNumbers(node1_1,node2_1))

int main() {
    ListNode *node1_1 = (ListNode *)malloc(sizeof(ListNode));
    ListNode *node1_2 = (ListNode *)malloc(sizeof(ListNode));
    ListNode *node1_3 = (ListNode *)malloc(sizeof(ListNode));
    node1_1->val = 2;
    node1_2->val = 4;
    node1_3->val = 3;
    node1_1->next = node1_2;
    node1_2->next = node1_3;

    ListNode *node2_1 = (ListNode *)malloc(sizeof(ListNode));
    ListNode *node2_2 = (ListNode *)malloc(sizeof(ListNode));
    ListNode *node2_3 = (ListNode *)malloc(sizeof(ListNode));
    node2_1->val = 5;
    node2_2->val = 6;
    node2_3->val = 4;
    node2_1->next = node2_2;
    node2_2->next = node2_3;

    free(node1_1);
    free(node1_2);
    free(node1_3);
    free(node2_1);
    free(node2_2);
    free(node2_3);

    print(addTwoNumbers(node1_1, node2_1));  <<== node1_1,node2_1, already freed
}

Instead do something like this

#include <iostream>
int main() {
    auto node1_1 = new ListNode;
    auto node1_2 = new ListNode;
    auto node1_3 = new ListNode;

    node1_1->val = 2;
    node1_2->val = 4;
    node1_3->val = 3;

    node1_1->next = node1_2;
    node1_2->next = node1_3;

    ListNode *node2_1 = new ListNode;
    ListNode *node2_2 = new ListNode;
    ListNode *node2_3 = new ListNode;

    node2_1->val = 5;
    node2_2->val = 6;
    node2_3->val = 4;

    node2_1->next = node2_2;
    node2_2->next = node2_3;

    std::cout << addTwoNumbers(node1_1, node2_1); 

    delete node1_1;
    delete node1_2;
    delete node1_3;
    delete node2_1;
    delete node2_2;
    delete node2_3;
}

1 Comment

good, that is what it is all about here at SO. sometimes people seem to forget that.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.