题目：输入一个链表，输出该链表中倒数第k个结点。
这个题的难点是几种特殊情况的判定
- head==null
- k < = 0;
- k > 链表的长度
以及对算法的一些简单求解
方法一：
import java.util.*;
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
Stack<ListNode> stack = new Stack<ListNode>();
while(head != null){
stack.push(head);
head = head.next;
}
if(stack.size() < k || k == 0){
return null;
}
for(int i = 0; i < k - 1; i++){
stack.pop();
}
return stack.pop();
}
}
利用栈的先进后出的特性进行求解。
方法二：
import java.util.*;
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode bHead = head;
if(head == null || k <= 0){
return null;
}
int first = 0;
while(first != k){
if(head == null){
return null;
}
head = head.next;
first++;
}
while(head != null){
head = head.next;
bHead = bHead.next;
}
return bHead;
}
}
使用两个指针一个指针先向前移动k - 1个节点，然后第二个指针和第一个指针一起移动，当第一个指针走到末尾的时候，第一个指针也就走到了倒数第k个节点了
当以第一个指针到达第k - 1个节点的时候，剩下的节点数为size - k个节点。
倒数第k个几点也就是正数第 size - k个节点， 主要思路就是让一个指针能够从head开始走size - k次就到达了倒数第k个节点了
