单链表 - push_back

Question

我必须创建方法 push_back，它将在我的列表末尾添加一个项目。但我有一个限制——我无法检查 head 是否为空（如果 head 为空）我不知道我该怎么做。这是我的代码：

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int value;
    struct node* next;
};


void print(struct node* head)
{
    struct node* iterator = head;

    while (iterator != NULL)
    {
        printf("%d\n", iterator->value);
        iterator = iterator->next;
    }
    printf("\n");
}

void pushBack(struct node** head, int value)
{
    struct node* element = (struct node*)malloc(sizeof(struct node));
    struct node* iterator = *head;

    element->value = value;
    element->next = NULL;

    if (iterator == NULL) //can't!
    {
        *head = element;
        return;
    }

    while (iterator->next != NULL)
    {
        iterator = iterator->next;
    }

    iterator->next = element;
}

int main(void)
{
    struct node* head = NULL;

    pushBack(&head, 4);
    pushBack(&head, 5);
    pushBack(&head, 52);
    pushBack(&head, 1);

    print(head);
    return 0;
}

关于如何在不检查头部且没有空节点的情况下使用 push_back 方法的任何想法？我的老师在类之后问我们讨论链表的地方，是否可以这样做 - 没有人知道如何做到这一点。

Answer 1

如果 head 指向列表中的最后一个元素，那么你只需说

newItem->next = head; 
head = newItem;

当然这个操作通常被称为"push"。我没听说过推回这个词。

Answer 2

这听起来像是一个数据结构问题 class。答案应该在阅读作业中。

但无论如何。我相信答案是使用循环链表。这是什么，是一个指向空节点的头指针。空节点标记列表的开始和结束。这样做可以简化所有的列表操作，因为它完全不需要对头指针进行操作。

Answer 3

当然可以。这是指向指针的指针的一个很好的用途。您甚至可以像这样使用 pushBack()：

pushBack(&(element->next), 4);

if element 是指向最后一个元素的指针！

如果您 return 来自 pushBack 的新元素，您可以在恒定时间 O(1) 内添加新元素，因为您不必遍历所有先前的元素。

Answer 4

我想你可能误解了导师的意愿。我相信老师希望你不要检查if (head)；而是检查 if (*head)。他们不是相同的条件。

在您的代码中，head 是指向指针的指针。尽管您可能迂腐地希望检查是否有人没有向您传递指向指针的空指针，但事实上您真正关心的是 it 指向的指针是否为空（因此取消引用).

这大大减少了您的代码沿袭。

void pushBack(struct node** head, int value)
{
    while (*head)
        head = &(*head)->next;

    *head = malloc(sizeof(**head));
    (*head)->value = value;
    (*head)->next = NULL;
}

单链表 - push_back

Singly linked list - push_back

c

linked-list

list

singly-linked-list