从单链表的尾部(或末尾)返回第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>列表长度等.这一个使用递归是干净的并涵盖所有这些情况.

Answer 1

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

你的内存使用得更多 - 确切地说是O(n).您正在创建一个等于列表中项目数的递归堆栈,这远非理想.

要从最后一个项目中找到第k个...

更好的(单遍历)解决方案 - 循环缓冲区:

使用O(k)额外内存.

有一个长度为k的数组.

对于每个元素,插入到数组的下一个位置(使用环绕).

最后,只需返回数组中下一个位置的项目.

2指针解决方案:

遍历列表两次,但仅使用O(1)额外内存.

从头开始p ₁和p ₂.

增加p ₁ k次.

而p ₁不在末尾
     增量p ₁和p ₂

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