查找链表的"从末尾开始的第N个节点"

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)算法.你现在做的很好.我认为没有令人信服的理由改变它.

Answer 2

开始两个指针.N向前移动前一个元素,然后移动每个指针1元素.当第一个指针到达结尾时,第二个指针将给出答案.

编辑:是的,它几乎与问题中给出的代码相同.但我觉得伪代码让它更清晰.要回答这个问题,没有其他的因为第一个N元素必须被访问两次.如果N很小则没关系.如果N大,则第二个循环将很小.所以它始终是一个O(n)解决方案.

Answer 3

保持两个节点间的2个指针.当第一个指针到达尾部时,第二个指针将指向所需的节点.

码:

typedef struct _node //define the list node
{
    int i;
    struct _node *next;
}    Node;



Node * findNode(Node *listHead, int n)
{
     Node *ptr1, *ptr2;  // we need 2 pointers
     ptr1 = ptr2 = listHead; // set the pointers to point to the list head initially

    while(ptr1->next != NULL) // keep looping until we reach the tail (next will be NULL for the last node)
    {
        if(n > 0)
        {
            ptr1 = ptr1->next; //increment only the 1st pointer
            n--;
        }
        else
        {
            ptr1 = ptr1->next; //increment both pointers
            ptr2 = ptr2->next;
        }
   }
   return ptr2;    //now return the ptr2 which points to the nth node from the tail

}