c++ - 在 C++ 中创建节点的不同方式感到困惑？

Question

我试图解决 leetcode 中的合并两个排序链表问题.

我解决了这个问题，但有一些我不理解的事情，当我尝试使用“new”关键字创建节点及其指针(它将节点存储在堆内存中)它可以工作，但是当我将其更改为首先创建节点，然后创建指向它的指针时，它会显示“stack-use-after-scope”。

这是注释的代码-

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

有人可以帮忙吗？

Answer 1

也许我们可以在这里简化我们的陈述。

这会简单地通过:

/**
 * 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;
    }
};

因为我们使用的是 Sentinel Node ，我们最终会返回 sentinel.next 而不是 head。

---

引用文献

• 有关更多详细信息，请参阅 Discussion Board在这里您可以找到大量解释良好的公认解决方案，其中包含各种 languages包括低复杂度算法和渐近算法runtime/memory分析 ^{1 , 2} 。