输入一个链表,输出该链表中倒数第k个结点。
注意:
k >= 0;
如果k大于链表长度,则返回 NULL;
样例
输入:链表:1->2->3->4->5 ,k=2
输出:4
(一) 解题思路
我们可以定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1,第二个指针保持不动;从第k步开始,第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1,当第一个(走在前面的)指针到达链表的尾结点时,第二个指针(走在后面的)指针正好是倒数第k个结点。
(二) 实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode findKthToTail(ListNode head, int k) {
if (head == null || k < 1) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while (k-- > 1) {
if (fast.next == null) {
return null;
}
fast = fast.next;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
|