Question

单链表尾插法为什么需要一个尾指针呢？

单链表尾插法为什么需要一个尾指针呢？如题。
头节点 A B 两个节点，再尾插一个C。
那不就是B的next指向C的地址，C的地址指向null吗。为什么需要一个尾指针？

头插法是
头节点 A B，插入C，A的next指向C，C的next指向B，相当于每次都把头节点和第一个节点断开插入一个吧。

Answer 1

只针对你的这个问题来说，你的思路没有问题，但是你的这个思路在代码里提现就必须要用到尾指针了，在循环创建单链表的时候，每个循环里的内容是必须要一样的吧？那么你必然会将新生成的结点放在头结点后边，而循环里如果都是这样不就成了头插法了嘛？即使你将第一个有效结点的生成抽出循环，那也就相当于从第一个节点开始了头插法，一句话说，思路没问题，实现起来需要多动动手，你问这个问题的时候应该还是新手，现在应该很厉害了，如果我的表达有错误也希望不吝赐教

Answer 2

最佳答案瞎说，因为链表不是随机存取的，尾指针减少时间成本

Answer 3

遍历链表的用来判断到达尾部。
比如：
node p=A;
while(p)
{
read(p);

p=p->next;

}

追问

…注意审题。

追答

尾部假如没有指针域，那他的数据结构就和普通节点不一致，那你是不是再给他定义一个尾部的特殊节点类型，并且维护他？那不多此一举

追问

单链表头插法不需要尾指针 尾插法需要，他这个尾指针是包含在头节点中 还是每一个node节点都包含一个尾指针呢

追答

每一个

Answer 4

如果不使用尾指针的话那么每次插入新的结点需要先遍历到链表的结尾位置，才能插入，时间复杂度就是O(n)；若使用指针记录尾部结点位置，那么插入的时间复杂度就是O(1)