c - 链表内存

Question

当下面的 intersect 函数中第一次调用 push 时，tail->next 的值为 NULL。我的理解是 &tail->next 将指向堆栈上虚拟对象的最后 4 个字节，该对象保存指向 next 的指针。现在，当 head_ref 在推送函数内更改时，我们是否会更改存储在虚拟对象的下一个变量中的地址？所以在我看来，dummy 总是指向列表的最后一个元素，即使这在执行时正确输出列表的头部。有人可以解释每次推送调用时内存中发生了什么吗？谢谢。

此问题摘自here

struct node* sortedIntersect(struct node* a, struct node* b)
{
    struct node dummy;
    struct node* tail = &dummy;
    dummy.next = NULL;

    while (a != NULL && b != NULL)
    {
        if (a->data == b->data)
        {
            push((&tail->next), a->data);
            tail = tail->next;
            a = a->next;
            b = b->next;
        }
        else if (a->data < b->data) /* advance the smaller list */
            a = a->next;
        else
            b = b->next;
    }
    return(dummy.next);
}

void push(struct node** head_ref, int new_data)
{
    struct node* new_node =
        (struct node*) malloc(sizeof(struct node));

    new_node->data = new_data;

    /* link the old list off the new node */
    new_node->next = (*head_ref);

    /* move the head to point to the new node */
    (*head_ref) = new_node;
}

Answer 1

虚拟人开始是这样的:

______     ______
|dummy| -> |NULL|
| 0   |    |    |
-------    ------

第一次调用push(&tail->next, a->data)后，我假设a->data是5 类似这样(请记住，此时 tail 指向 dummy):

 ______    _________      _____
|dummy| -> |new_node| -> |NULL|
|  0  |    |   5    |    |    |
 -----     ---------     ------

然后我们调用 tail = tail->next; 这将导致 tail 指向 new_node，这就是为什么，当我们再次调用 push(&tail->next, a->data)，new_node 数字 2 将插入到旧 new_node 和 之间>NULL

最后我们调用return dummy->next，这将返回链表，最近添加的节点位于第一位。虚拟对象本身将被删除，因为它是在堆栈上分配的。

如果我们这样写，push 函数就会变得更加清晰:

void push(struct node** head_ref, int new_data)
{
    struct node* new_node =
        (struct node*) malloc(sizeof(struct node));

    new_node->data = new_data;

    /* save old head */
    struct node* old_head = *head_ref;

    /* move the head to point to the new node */
    *head_ref = new_node;

    /* link the old list off the new node */
    new_node->next = old_head;
}