您如何从单链表的尾部得到n个节点(一次遍历)? [英] How would you get the nth node from the tail in a singly linked list (in one traverse)?

问题描述

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

So I got this question from an exam.

如何从单链列表的末尾得到第n个节点?

How would you get the nth node from the tail in a singly linked list?

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

Each Node has a value and a next (which is a pointer to the next value). We are given this:

getNodeFromTail(Node head, int x) {

}

所以我做的方法是遍历一次来找到列表的长度.然后再次获取(length-x)节点.因此，总共有2次遍历.

So the way I did it is to find the length of the list by traversing it once. Then going again to get the (length - x) node. So in total, 2 traversals.

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;
}

这是正确的，但是还有一个额外的问题，询问我们是否可以做同样的事情，但只能遍历一次.在考试期间我没想到，但是在想到了一种方法之后，但我不太确定.

This is right, but there is also a bonus question that is asking whether we can do the same thing, but only traversing it once. I couldn't think of it during the exam, but after I thought of one way, but I'm not too sure about it.

我可以制作一个长度为x的ArrayList.然后，每次运行while循环时，我都会在数组顶部添加一个元素，向下层叠并开始执行数组的最后一个元素.然后，当头部撞到空位时，返回数组[x-1]处的节点.

I could make an ArrayList of length x. Then every time I run the while-loop, I would add an element to the top of the array, cascade down and kick off the last element of the array. Then when the head hits null, return the node at the array[x-1].

这是对的吗?有更好的解决方案吗?

Is this right? Is there a better solution?

推荐答案

1. 使2个指针指向第一个节点
2. 按x
前进一个指针
3. 两个指针并排前进，直到列表中的另一个指针结束.
4. 您的指针进一步向后指向最后一个x元素.

1. Make 2 pointers to the first node
2. Advance one pointer by x
3. Advance both pointers side by side until the one further in the list hits the end.
4. Your pointer further back points to the xth last element.

这篇关于您如何从单链表的尾部得到n个节点(一次遍历)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！