实现算法以查找单链列表的第k个元素 [英] Implement an algorithm to find the kth to last element of a singly linked list

问题描述

实施一种算法来查找单链列表的第k个元素.

Implement an algorithm to find the kth to last element of a singly linked list.

对于上述问题，将链接列表反转然后再次遍历并获取第k个元素，是否是一个很好的解决方案?

Is a good solution to the above problem, reversing the linked list then traversing again and getting the kth element?

推荐答案

首先，列表是单链接.因此，这是一个很好的提示，您不应尝试撤消它，因为制作副本需要大量的存储空间.

First of all the list is singly-linked. So that is a good hint that you should not try to reverse it, because you would need as much storage to make the copy.

您可以使用龟兔算法的修改版本:

You can use a modified version of the turtle-hare algorithm:

• 在列表的开头使用 hare 指针
• 将其至少移出 K 个元素
• 如果您之前点击了 last 元素，那么您将无法找到最后一个元素的 Kth.
• 在列表的开头放置 turtle 指针
• 现在将 hare 指针运行到列表的末尾，每当您移动 hare 指针时，就会移动 turtle .
li>

• Use a hare pointer at the start of the list
• Move it at least K elements away
• If you hit the last element before, then you cannot find the Kth to last element.
• Place a turtle pointer at the start of the list
• Now runs the hare pointer to the end of the list, each time you move the hare pointer, moves the turtle.

当 hare 指针到达链表末尾时，turtle 位于 Kth 到最后一个元素上.

When the hare pointer reach the end of the list, the turtle is on the Kth to last element.

这篇关于实现算法以查找单链列表的第k个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！