1

【面试题】

编写一个函数，该函数将在一次传递中返回从整数单链表的尾部（或结尾）开始的第 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 > 列表长度等。这个采用递归的方法很干净，涵盖了所有这些情况。

4

2 回答 2

5

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

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

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

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

使用 O(k) 额外内存。

有一个长度为 k 的数组。

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

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

2指针解决方案：

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

在开头开始 p 1和 p 2。

将 p 增加1 k 倍。

而 p 1不在末尾
     增量 p 1和 p 2

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

于 2013-03-02T20:36:37.733 回答
0 
'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;
于 2013-03-03T04:34:02.437 回答