n****n
发帖数: 568 | 1 2.2 implement an algorithmm to find the kth to last element of a singly
linked list.
我翻了翻答案，好几种，难道不是直接遍历把linked list的长度算出来，再traverse
n-k步拿到kth to last element吗？这个算法又直接，时间上不比那几个solution差，
难道我哪里想错了？ |
g****y
发帖数: 2810 | 2 时间复杂度是一样的，但是如果链表不是在内存中，而是一个流或者是序列化在外存
储器上的话，读两遍的消耗就会比较大，所以就要只读一遍。 |
n****n
发帖数: 568 | 3 “你是不是‘永远’都会为了效率牺牲可读性”？
【在 g****y 的大作中提到】
: 时间复杂度是一样的，但是如果链表不是在内存中，而是一个流或者是序列化在外存
: 储器上的话，读两遍的消耗就会比较大，所以就要只读一遍。
|
p*****2
发帖数: 21240 | 4 刚才看了一下，你这个问题CC150已经有解答了。 |
z****e
发帖数: 54598 | 5 第四版就有了，很老的问题了
不过楼主问的意思大概是
既然不增加复杂度，为什么不用相对更简洁明了的方式？
从某种意义上说，楼主未必错，软件工程里面就很强调代码的可读性
因为跟维护成本呈最直接的相关
能领悟到这一层，楼主有一定悟性
面试时候要看对方想知道什么
如果可能的话，先给一个最简单的解决方案
然后如果对方要求，再逐步深入
如果一上来就给出貌似很高明的解决方案，下一个问题估计就是
这题你是不是做过？来，我们换一题
【在 p*****2 的大作中提到】
: 刚才看了一下，你这个问题CC150已经有解答了。
|
p*****2
发帖数: 21240 | 6
我说的意思就是CC150已经回答了LZ的问题了，不是这个题目的解答。
【在 z****e 的大作中提到】
: 第四版就有了，很老的问题了
: 不过楼主问的意思大概是
: 既然不增加复杂度，为什么不用相对更简洁明了的方式？
: 从某种意义上说，楼主未必错，软件工程里面就很强调代码的可读性
: 因为跟维护成本呈最直接的相关
: 能领悟到这一层，楼主有一定悟性
: 面试时候要看对方想知道什么
: 如果可能的话，先给一个最简单的解决方案
: 然后如果对方要求，再逐步深入
: 如果一上来就给出貌似很高明的解决方案，下一个问题估计就是
|
n****n
发帖数: 568 | 7 我手头上这本是最新的版本，让我们来看看solution #3:
A more optimal, but less straightforward solution is to implement this
iteratively. We can use two pointers, p1 and p2. We place them k nodes apart
in the linked list by putting p1 at the beginning and moving p2 k nodes
into the list. Then, when we move them at the same space, p2 will hit the
end of the linked list after length-k steps. At that point, p1 will be
Length-k nodes into the list, or k nodes from the end.
在我看来，the sum of total move is 2*Length-k for both p1 and p2.如果是这样
，直接算出Length of linked list 长度，然后用所谓的trivial solution 1,其实两
者的running time是一样的，但后者显然更直接，让容易理解
【在 p*****2 的大作中提到】
:
: 我说的意思就是CC150已经回答了LZ的问题了，不是这个题目的解答。
|
h******s
发帖数: 86 | 8 2楼说的行吗
apart
【在 n****n 的大作中提到】
: 我手头上这本是最新的版本，让我们来看看solution #3:
: A more optimal, but less straightforward solution is to implement this
: iteratively. We can use two pointers, p1 and p2. We place them k nodes apart
: in the linked list by putting p1 at the beginning and moving p2 k nodes
: into the list. Then, when we move them at the same space, p2 will hit the
: end of the linked list after length-k steps. At that point, p1 will be
: Length-k nodes into the list, or k nodes from the end.
: 在我看来，the sum of total move is 2*Length-k for both p1 and p2.如果是这样
: ，直接算出Length of linked list 长度，然后用所谓的trivial solution 1,其实两
: 者的running time是一样的，但后者显然更直接，让容易理解
|
n****n
发帖数: 568 | 9 2楼说的也不错，但实际上题目并没有这个假设。
【在 h******s 的大作中提到】
: 2楼说的行吗
:
: apart
|
p***e
发帖数: 9 | |
s*w
发帖数: 729 | 11 很多题目语焉不详，没说额外的附加要求。按书里的说法，这是让读者熟悉真实面试的
风格。的确如此；不过问题是读者阅读的时候常常无人可问，不得不翻答案搞清楚题目
的用意。【 在 neiman (marcus) 的大作中提到: 】
traverse |
p*****2
发帖数: 21240 | 12 LZ你的问题，CC150已经有解答了，你仔细看一下。CC150的意思是太trivial了，肯定
不是面试官想考你的方向。 |
