What's wrong in the following merging sorted array C++ code?

Question

I have been implementing a merging sorted array problem in C++, and found something strange happened in my code. So, here is my code.

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if (l1 == NULL)
            return l2;
        else if (l2 == NULL)
            return l1;
        else
        {
            ListNode *head, *p;
            ListNode *h1 = l1;
            ListNode *h2 = l2;
            if (h1->val <= h2->val)
            {
                ListNode newNode(h1->val);
                head = &newNode;
                h1 = h1->next;
            }
            else
            {
                ListNode newNode(h2->val);
                head = &newNode;
                h2 = h2->next;
            }
            p = head;
            while (h1 != NULL && h2 != NULL)
            {
                if (h1->val <= h2->val)
                {
                    ListNode *Node = new ListNode(h1->val);
                    p->next = Node;
                    //p = p->next;
                    h1 = h1->next;
                }
                else
                {
                    ListNode *Node = new ListNode(h2->val);
                    p->next = Node;
                    //p = p->next;
                    h2 = h2->next;
                }
                p = p->next;
            }
            if (h2 != NULL)
            {
                while (h2 != NULL)
                {
                    ListNode *Node = new ListNode(h2->val);
                    p->next = Node;
                    p = p->next;
                    h2 = h2->next;
                }
            }
            else if (h1 != NULL)
            {
                while (h1 != NULL)
                {
                    ListNode *Node = new ListNode(h1->val);
                    p->next = Node;
                    p = p->next;
                    h1 = h1->next;
                }
            }
            return head;
        }
    }
};

int main()
{
    ListNode A1(1);
    ListNode A2(2);
    ListNode A3(3);
    ListNode A4(5);
    ListNode A5(7);
    A1.next = &A2;
    A2.next = &A3;
    A3.next = &A4;
    A4.next = &A5;
    ListNode B1(2);
    ListNode B2(4);
    ListNode B3(6);
    ListNode B4(8);
    ListNode B5(10);
    B1.next = &B2;
    B2.next = &B3;
    B3.next = &B4;
    B4.next = &B5;
    Solution solution;
    ListNode *x = solution.mergeTwoLists(&A1, &B1);
    while (x != NULL)
    {
        cout << x->val << endl;
        x = x->next;
    }
    return 0;
}

This code will get a runtime error. When I debugged it in codeblocks, I found everything normal in class Solution.When it comes to main function, the while loop, something abnormal happened! x points to some strange address after one loop. I'm wondering what's wrong.

Answer 1

Thé first problem I see un jour code is that you keep adresses to stack allocated variables:

ListNode *head, *p;
// ...
if (h1->val <= h2->val) {
   ListNode newNode(h1->val);
   head = &newNode;
   h1 = h1->next;
   // newNode is destroyed here
   // thus head now points to invalid
   // data
} else {
   // same kind of code
}
p = head;
// p does not point to anything useful

This is what's wrong with your code.

Linked lists like the one you are implementing with ListNode are typically implemented using dynamically allocated nodes. You should try it here too. I suggest that you implement the most basic algorithms for your linked list (insertion, removal, search) before the merge, thus you'll be more likely to grope this structure.

Answer 2

Here, in mergeTwoLists:

    if (h1->val <= h2->val)
    {
        ListNode newNode(h1->val);
        head = &newNode;
        h1 = h1->next;
    }
    else
    {
        ListNode newNode(h2->val);
        head = &newNode;
        h2 = h2->next;
    }

All of the other nodes you create on the heap with new, but here you create newNode on the stack. It's the first node of the list you're building, and it's a local variable of mergeTwoLists. When control passes out of the function, that first node passes out of scope. Then you access it and dereference its next in main, which is undefined behavior.

Answer 3

Try using this

while (x->next != NULL)