相关疑难解决方法(0)

这似乎正在回答正确的答案,但我不确定这是否真的是最好的方法.好像我正在访问前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;
}

[面试问题]

编写一个函数,在一次传递中从单个链接的整数列表的尾部(或结尾)返回第5个元素,然后提供一组针对该函数的测试用例.

它类似于问题:如何从单链表的末尾找到第n个元素？,但我有一个额外的要求,我们应该只遍历一次链表.

这是我的解决方案:

struct Lnode  
{
    int val;
    Lnode* next;
    Lnode(int val, Lnode* next=NULL) : val(val), next(next) {}
};


Lnode* kthFromTail(Lnode* start, int k)
{
   static int count =0;
   if(!start)
        return NULL;

   Lnode* end = kthFromTail(start->next, k);
   if(count==k) end = start;
   count++;
   return end;
}

我只遍历链表并使用隐式递归堆栈.另一种方法可能是有两个指针:快速和慢速,快速的指针比慢指针快.一个似乎更好？我认为具有两个指针的解决方案将很复杂,例如:奇数长度列表,甚至长度列表,k>列表长度等.这一个使用递归是干净的并涵盖所有这些情况.