破解编码采访，第6版- Q: 2.2
破解编码采访，第6版- Q: 2.2
提问于 2015-09-08 21:54:13
问题是将kth返回到单个链接列表的最后一个元素。所有建议的解决方案都相当复杂，我不知道为什么我的解决方案无效。谁能告诉我原因吗？
public class CrackTheInterview {
/**
* @param args the command line arguments
*/
public static Node kthToLast(Node n, int k) //pass in LinkedList's head node
{
int counter = 1;
while (n.next != null)
{
n = n.next;
}
//at the end of the while loop, n equals the last node in the LinkedList
while (counter != k)
{
n = n.previous;
counter++;
}
//now node n is the kth node from the end
return n;
}
}class Node
{
Node next = null;
Node previous = null;
int data;
public Node (int d)
{
this.data = d;
}
}回答 3
Stack Overflow用户
回答已采纳
发布于 2015-09-08 21:55:42
单链接列表不会同时具有next和previous。您有一个双链接列表，这显然使这个问题更容易解决。
Stack Overflow用户
发布于 2015-09-08 23:43:09
我没有那本书，所以我不知道里面会有什么复杂的解决方案，但以下两个手指的解决方案对我来说似乎很简单，除了使用单链接列表之外，与你的没有什么不同：
/* Returns the kth last node in the list starting at n.
* If the list is empty (n == null) returns null.
* If k is <= 1, returns the last node.
* If k is >= the number of nodes in the list, returns the first node.
*/
public static Node kthToLast(Node n, int k) {
Node advance = n;
while (--k > 0 && advance != null) {
advance = advance.next;
}
/* Now advance is k nodes forward of n. Step both in parallel. */
while (advance != null) {
advance = advance.next;
n = n.next;
}
return n;
}Stack Overflow用户
发布于 2018-02-11 19:15:04
书中的第一个解决方案是：
解决方案1:如果已知链接列表大小 如果已知链表的大小，则kth到last元素是(length - k)th元素。我们只需遍历链接列表就可以找到这个元素。因为这个解决方案太琐碎了，我们几乎可以肯定这不是面试官想要的。
但是我们可以很容易地通过一次就找到链接列表的大小！因此，修改OP的问题，我会问下面的答案有什么问题？
我们用两个指针。使用一个查找链接列表的大小，使用另一个查找(size - k)步骤。
(用Python实现)
def kth_to_last(head, k):
p1 = head
p2 = head
counter = 0
while p1.nxt is not None: # calculating the size of the linked list
p1 = p1.nxt
counter += 1
for _ in range(counter - k):
p2 = p2.nxt
return p2.val页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/32467864
复制相关文章
相似问题
腾讯云开发者
