思路:
带头结点还是不带头结点的链表?不用纠结,随便确定一个,就以不带头结点为例。
- 首先想到的是用两个指针遍历链表。一个走的快遍历整个链表并统计出链表有多少个结点;另一个是达到一定条件开始遍历链表,当快指针遍历完整个链表的时候,慢指针刚好停在我们需要的倒数第K个。
- 那我们就需要确定几个条件,快指针是走到最后一个结点停下,还是走到最后一个结点后面的空结点停下?这将决定了我们的慢指针什么时候开始走。
答案:
以快指针走到null停下为例:
快指针停在null,慢指针刚好停在倒数第K个结点。
此时就它两的距离是K,所以我们设置慢指针开始走的条件应该是快指针走了K步之后。第K+1步的时候,快慢指针一起走。
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
//初始化两个指针
ListNode p,target;
p = head;
target = head;
//用于统计快指针走的步数
int i = 0;
//当快指针指向null时,停止循环
while(p != null){
//当i大等k时,目标指针开始走
/*这个判断写在最前面,逻辑会清晰点:
不会漏掉对i=0时p、target都指向head时,target能不能走的判断*/
if(i >= k){
target = target.next;
}
//快指针指向下一个结点
p = p.next;
//i加一
i++;
}
//如果i小于k,说明输入了k大于总结点数,返回null
if(i < k){return null;}
//否则返回目标结点
return target;
}
}这道题还可以用栈、集合来解。

京公网安备 11010502036488号