返回单链表尾部(或末端)的第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

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

使用了更多的内存——确切地说是O(n)。您正在创建一个与列表中的项数相等的递归堆栈，这远非理想。

从上一项开始查找第k项…

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

使用O(k)额外内存

有一个长度为k的数组

对于每个元素，在数组的下一个位置插入(使用换行)。

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

解决方案:投球

遍历列表两次，但只使用O(1)额外内存。

开始p₁和p₂。

增加p₁ k次。

而p₁不在末尾
,,,,增加p <子> 1 和2 p <子>

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

Answer 2

'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;