思路:
带头结点还是不带头结点的链表?不用纠结,随便确定一个,就以不带头结点为例。
- 首先想到的是用两个指针遍历链表。一个走的快遍历整个链表并统计出链表有多少个结点;另一个是达到一定条件开始遍历链表,当快指针遍历完整个链表的时候,慢指针刚好停在我们需要的倒数第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; } }
这道题还可以用栈、集合来解。