链表中倒数第k个结点

题目描述：输入一个链表，输出该链表中倒数第k个结点。

思路：指向首结点的第1个指针走k-1步，如果后继结点为空，则返回null，第1个指针指向第k个结点。指向首结点的第2个指针与第1个指针同步遍历，当第1个指针指向最后一个结点时，第2个指针走了n-k步，指向了倒数第k个结点（n-(n-k+1)=k-1，倒数第1个结点与倒数第k个结点相差k-1步）。

步骤：

1 如果首结点为空或者k<=0，返回null。

2 指向首结点的第1个指针走k-1步。

3 指向首结点的第2个指针与第1个指针同步遍历，直到第1个指针指向最后一个结点。

4 返回第2个指针指向的结点。

时间复杂度：O(n)。

Java代码：

/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode FindKthToTail(ListNode head,int k) {// 如果首结点为空或者k<=0，返回nullif (head == null || k <= 0) {return null;}// 第1个指针指向首结点ListNode first = head;// 走k-1步，第1个指针指向第k个结点for (int i = 1; i < k; i++) {// 后继结点不能是nullif (first.next == null) {return null;}first = first.next;}// 第2个指针指向首结点ListNode second = head;// 当第1个指针指向最后一个结点时，第2个指针走了n-k步，指向了倒数第k个结点// n-1-(n-k)=k-1// 倒数第1个结点与倒数第k个结点相差k-1步while (first.next != null) {first = first.next;second = second.next;}return second;}
}