c++ - 查找链表的 "Nth node from the end"

Question

这似乎返回了正确的答案，但我不确定这是否真的是处理事情的最佳方式。好像我访问前 n 个节点的次数太多了。有什么建议么？请注意，我必须使用单链表来执行此操作。

Node *findNodeFromLast( Node *head, int n )
{
    Node *currentNode;
    Node *behindCurrent;
    currentNode = head;
    for( int i = 0; i < n; i++ ) {
        if( currentNode->next ) {
            currentNode = currentNode->next;
        } else {
            return NULL;
        }
    }

    behindCurrent = head;
    while( currentNode->next ) {
        currentNode = currentNode->next;
        behindCurrent = behindCurrent->next;
    }

    return behindCurrent;
}

Answer 1

另外一种不用两次访问节点的方法如下:

创建一个大小为 n 的空数组，从索引 0 开始指向该数组的指针，并从链表的开头开始迭代。每次访问一个节点时，将其存储在数组的当前索引中并推进数组指针。当您填充数组时，环绕并覆盖您之前存储的元素。当您到达列表末尾时，指针将指向列表末尾的元素 n。

但这也只是一个 O(n) 算法。你现在做的很好。我认为没有令人信服的理由来改变它。