c - 删除链表的最后一个节点。每个节点都有一个数据指针，指向一些数据

Question

大家好我在一个技术面试中被问到的网站上看到了这个问题

节点有一个数据指针，也指向一些数据。

谁能帮我详细理解这个问题的意思？？

这是否意味着 Node 有指向另一个节点的指针，也指向其他一些数据节点。并且该数据节点不指向任何其他节点。在那种情况下，我们的节点将有两个指针。

我真的很困惑。请帮忙。

提前致谢

Answer 1

您的列表的节点结构非常清晰。在 C 中，它看起来类似于:

typedef struct list list;
struct list {
        list *next;
        void *data;
}

但是，如果你的任务是删除一个链表的最后一个节点，那么这个任务就是不明确的。在单链表中，通常在最前面插入新节点，因为这可以在常数时间内完成。因此，尚不清楚“最后一个节点”是指最近插入的节点(因此是前端节点)还是指插入的第一个节点(因此是您在执行时看到的最后一个节点)遍历列表)。

在第一种情况下，删除列表 list 的“最后一个”节点真的很容易，因为它是前面的节点:list = list->next。您可能希望合并空列表的边缘情况:list = list?list->next:NULL。

在第二种情况下，您应该删除首先插入的节点，这有点棘手。您必须遍历列表，维护指向当前元素的指针以及指向之前元素的指针。以下是一些您可能会觉得有用的代码:

cur = list->next;
prev = list;

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

prev->next = NULL;

free(cur->data);
free(cur);

此代码遍历列表并在 cur 指向最后一个节点(下一个指针指向 NULL 的唯一列表节点)时停止。然后，我们通过将前一个元素的下一个指针设置为 NULL 来取消链接最后一个节点。

请注意，您有两种特殊情况:
- 该列表最初是空的(此处无事可做)
- 列表只包含一个元素(即第一个元素是最后一个元素，切换到前面描述的方法)