12、链表中倒数第k个结点
题目
输入一个链表，输出该链表中倒数第k个结点。
思路
为了能够只遍历一次就能找到倒数第k个节点，可以定义两个指针：
（1）第一个指针从链表的头指针开始遍历向前走k-1，第二个指针保持不动；
（2）从第k步开始，第二个指针也开始从链表的头指针开始遍历；
（3）由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。
下图展示了在有6个结点的链表上找倒数第3个结点的过程
代码
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
//遍历整个链表长度length，如果给出的k值大于length，那么直接出错
int length =0;
ListNode head1 = head;
while(head1!=null){
length++;
head1 = head1.next;
}
if(k<=0 || k>length)
return null;
//找到链表的第一个和第二个指针，分别为ahead和behind
ListNode ahead = head;
ListNode behind =head;;
//将ahead的位置移到k-1 位置，此时链表起始位为behind
for(int i=0;i<k-1;i++){
if(ahead.next!=null){
ahead = ahead.next;
}
}
//使用ahead遍历剩下的链表长度，如果ahead到达末尾，那么behind到达的位置就是倒数第K个节点
while(ahead.next!=null){
ahead = ahead.next;
behind = behind.next;
}
return behind;
}
}
投递字节跳动等公司8个岗位