从结束寻找“第N个节点”的链表 [英] Finding the "Nth node from the end" of a linked list

问题描述

这似乎是返回正确的答案，但我不知道这是否真的是最好的方式去处理事情。它似乎我访问第一个n节点太多次。有什么建议么？注意，我必须用一个单独的链表来做到这一点。

This seems to be returning the correct answer, but I'm not sure if this is really the best way to go about things. It seems like I'm visiting the first n nodes too many times. Any suggestions? Note that I have to do this with a singly linked list.

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

推荐答案

访问节点两次如下：

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

Create an empty array of size n, a pointer into this array starting at index 0, and start iterating from the beginning of the linked list. Every time you visit a node store it in the current index of the array and advance the array pointer. When you fill the array, wrap around and overwrite the elements you stored before. When you reach the end of the list, the pointer will be pointing at the element n from the end of the list.

但这也只是一个O（n）算法。你现在做的是好的。我没有看到任何令人信服的理由改变它。

But this also is just an O(n) algorithm. What you are currently doing is fine. I see no compelling reason to change it.

这篇关于从结束寻找“第N个节点”的链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！