在c++中使用单独的funciton进行内存分配。

Question

我有cplus的代码，可以制作单项链接的列表。

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

使用下面的函数。

static void push_list(struct ListNode*& _head, int _val)
{

    if (NULL == _head)
        _head = new ListNode(_val);

    else{
        ListNode* tmp = _head->next;
        while (tmp != NULL)
            tmp = tmp->next;
        tmp = new ListNode(_val);
    }
}

但是，它只分配了一个元素，而且head->next保持为NULL。

该函数调用如下。

static void MakeList(void)
{
    ListNode* l1 = NULL;
    push_list(l1, 1);
    push_list(l1, 2);
    push_list(l1, 3);
    push_list(l1, 4);
}

Answer 1

你的 push_list() 是执行错误的。

当 _head 是空的，您可以创建一个新节点，并将其分配给 _head. 到目前为止，OK。

但在随后的通话中，当 _head 不为空，您是将 _head->next 到 tmp和 _head->next 当列表中有1个节点时，将为空。 所以，你的 while 循环不做任何事情，留下 tmp 设置为null (即使列表中有多个节点，你的循环最终也会到达最后一个节点，并设置 tmp 到其 next因此 tmp 无论是否进入循环，最终都将为空）。) 然后你创建一个新节点，并将其分配给 tmp 仅仅是，不对 next 列表中最后一个节点的字段。 所以，你已经泄露了新的节点，并且 _head->next 下一次仍为空 push_list() 被调用，一次又一次地造成同样的问题。

为了解决这个问题，你需要调整你的循环，找到列表中的最后一个节点，然后你可以将新节点分配给最后一个节点的 next 字段，例如。

static void push_list(ListNode* &_head, int _val)
{
    if (!_head)
        _head = new ListNode(_val);
    else{
        ListNode* tmp = _head; // <-- not _head->next !
        while (tmp->next) { // <-- while there is still another node in the list...
            tmp = tmp->next;
        }
        // tmp now points to the last node, not to null !
        tmp->next = new ListNode(_val);
    }
}

---

push_list() 可以通过使用一个稍微不同的，更优化的循环策略来进一步简化。

static void push_list(ListNode* &_head, int _val)
{
    ListNode** tmp = &_head;
    while (*tmp) {
        tmp = &((*tmp)->next);
    }
    *tmp = new ListNode(_val);
}

这个循环可以找到第一个 ListNode* 指针是空的，然后给这个指针分配一个新的节点。 这样一来，你就不必再把它当作 _head 分别。 要么 _head 本身将为空，或者 next 列表中最后一个节点的字段将为空。 这个第一个可用的空值就是你要插入新节点的地方。