寻找“从末端开始的第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;
}

推荐答案

另一种无需两次访问节点的方法如下:

Another way to do it without visiting nodes twice is as follows:

创建一个大小为 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屋！