java - 关于链表3元素

Question

我是数据结构世界的新手并正在学习它，我有一个关于链表的查询，因为在一次采访中，有人问它与链表的上下文是如何在链接的末尾找到第三个元素一口气列出来，我不知道这个请指教。

Answer 1

我假设您列表中的第一个节点称为head。

所以设置一个指向head的指针，我们称之为current

Node current = head;

然后再做一个指向前面三个位置的指针

Node threeAhead = head.next.next.next;

然后编写一个循环，首先检查threeAhead.next是否为空，如果不是：

threeAhead = threeAhead.next;
curr = curr.next;

当threeAhead.next 变为null 时，您距离当前的末尾三个位置。

Answer 2

if(node.next.next.next == null)

这有点脏，但基本上我只是检查下线的节点 3 节点是否为空。如果是的话，你已经从最后得到了第三个。当然，这还没有考虑大小小于 3 的列表。

Answer 3

如果您在开始之前知道列表的长度，请使用 JB Nizet 的方法

node = first;
for (i = 0; i < length - N_FROM_END; i++) {
    node = node.next;
}

result = node.value

如果你现在不知道长度：

nodes = new Node[N_FROM_END];
node = first;
for (i = 0; node != null; i++) {
    nodes[i % N_FROM_END] = node;
    node = node.next;
}
result = nodes[i % N_FROM_END].value

或类似的东西。（检查边界条件......并说明列表长度小于N_FROM_END。）

两个答案都满足“最多访问一次节点”约束。