algorithm - 您将如何从单向链表(一次遍历)中的尾部获取第 n 个节点？

Question

所以我从考试中得到了这个问题。

如何从单向链表的尾部获取第 n 个节点？

每个节点都有一个值和一个下一个(它是指向下一个值的指针)。我们得到了这个:

getNodeFromTail(Node head, int x) {

}

所以我的做法是遍历一次求出list的长度。然后再去获取 (length - x) 节点。所以总共有 2 次遍历。

getNodeFromTail(Node head, int x) {
    int length = 0;
    Node headdupe = head;
    while (headdupe.next != NULL) {
         headdupe = headdupe.next;
         length++;
    }
    int a = length--;
    for (int y = 0; y < a; y++) {
         head = head.next;
    }
    return head;
}

这个是对的，但是还有一个bonus question是问我们是否可以做同样的事情，但是只遍历一次。考试的时候想不出来，想了一个办法之后，又不太确定。

我可以创建一个长度为 x 的 ArrayList。然后每次我运行 while 循环时，我都会将一个元素添加到数组的顶部，向下级联并启动数组的最后一个元素。然后当头部命中 null 时，返回数组 [x-1] 处的节点。

这样对吗？有更好的解决方案吗？

Answer 1

1. 制作2个指向第一个节点的指针
2. 将指针前进一个x
3. 并排推进两个指针，直到列表中更远的指针到达末尾。
4. 您的指针向后指向第 x 个最后一个元素。