返回单链表尾部（或尾部）的第k个元素

Question

[采访问题]

编写一个函数，该函数将在一次传递中从单个链表整数的尾部（或尾部）返回第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个指针。哪一个看起来更好？我认为有两个指针的解决方案会很复杂，因为有很多例子，比如奇数长度列表，偶数长度列表，k

Answer 1

'n' is user provided value. eg, 5 from last.

int gap=0 , len=0;
myNode *tempNode;

while (currNode is not NULL)
{
 currNode = currNode->next;
 gap = gap+1; 
 if(gap>=n)
   tempNode = currNode;
}
return tempNode;

Answer 2

2指针解决方案不符合您的要求，因为它会遍历列表两次。

你的使用了更多的内存——确切地说是O（n）。您正在创建一个递归堆栈，其数量等于列表中的项数，这远远不够理想。

要从最后一项中查找第k项。。。

更好的（单次遍历）解决方案-循环缓冲区：

使用O（k）额外内存。

具有长度为k的数组。

对于每个元素，在数组的下一个位置插入（使用环绕）。

最后，只需将项目返回到数组中的下一个位置。

2点解决方案：

遍历列表两次，但仅使用O（1）个额外内存。

在开始处开始p₁和p₂。

增加p₁k倍。

而p₁不在末尾

p₂指向最后一个元素的第k个。