Return Kth to Last: Implement an algorithm to find the kth to last element of a singly linked list.
解答1
两指针p1和p2，p2比p1多k-1步，两个同时走，当p2到底多时候，p1就是倒数第k个元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public Node lastKth(Node head, int k) {
Node p2 = head;
while (k - 1 > 0) {
if (p2 == null) {
return null;
}
p2 = p2.next;
k--;
}
Node p1 = head;
while (p2.next != null) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
|
时间复杂度：O(k - 1 + n - k) = O(n)
空间复杂度：O(1)
解答2
用递归，这个问题就变成如何计算每个元素位于倒数第几，最后一个元素位于倒数第1，倒数第二个元素等于前一个元素的位数+1……：
1
2
3
4
5
6
7
8
9
10
|
public int lastKth(Node head, int k) {
if (head == null) {
return 0;
}
int index = lastKth(head, k) + 1;
if (index == k) {
print(head);
}
return index;
}
|
不过上面的办法不好，因为它没有返回Node，而是打印出来。看下面这个方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public class Index {
int value;
}
public Node lastKth(Node head, int k, Index index) {
if (head == null) {
return null;
}
Node node = lastKth(head.next, k, index);
index.value = index.value + 1;
if (index.index == k) {
return head;
}
return node;
}
|
空间复杂度：O(n)，每层递归都hold住变量了
时间复杂度：O(n)，肯定会从头递归到底。
评论