Implement an algorithm to find the kth to last element of a singly linked list.
Hint
- What if you knew the linked list size? What is the difference between finding the Kth-to-last element and finding the Xth element?
- If you don't know the linked list size, can you compute it? How does this impact the runtime?
- Try implementing it recursively. If you could find the (K -1)th to last element, can you find the Kth element?
- You might find it useful to return multiple values. Some languages don't directly support this, but there are workarounds in essentially any language. What are some of those workarounds?
- Can you do it iteratively? Imagine if you had two pointers pointing to adjacent nodes and they were moving at the same speed through the linked list. When one hits the end of the linked list, where will the other be?
Solution
首先来看迭代的方法，链表类问题很多可以通过多个指针同时遍历来解决。假设链表长度为 n，那么倒数第 k 个结点也就是第 n - k 个结点所指向的结点。所以首先让一个快指针遍历 k 个位置，然后再开始让慢指针一起遍历，当快指针达到链表尾部时，慢指针的结点就是我们要找的位置。
public ListNode findLastKthNode(ListNode head, int k) {
ListNode slowNode = head, fastNode = head;
while (k-- > 0) {
if (fastNode == null && k >= 0) return null; // 此时 k > n, 不存在
fastNode = fastNode.next;
}
while (fastNode != null) {
fastNode = fastNode.next;
slowNode = slowNode.next;
}
return slowNode;
}
再来看递归的解法，直接递归到结尾，利用一个变量 count 计数
private int count = 0;
public ListNode findLastKthNode(ListNode head, int k) {
if (head == null)
return null;
ListNode node = findLastKthNode(head.next, k);
count++;
if (count == k) return head;
if (count < k) return null;
return node;
}
