1、设两个指针slow和quick,当i<k-1 时slow移动,quick不动。当i>=k-1 时quick也开始同频率移动;
2、当slow移动到正序第k个,quick移动到正序第一个;
3、当slow移动到倒序第一个,quick移动到 倒序第k个;
4、return quick
* 题目:给出链表 {1,2,3,4,5,6,7},输出倒序第5个
* 当slow移动到5,quick移动到1
* 当slow移动到7,quick移动到3(倒数第5个)
* 1 2 3 4 5 6 7
* q s # 开始时slow=5;quick=1
* q s # 结束时show+2=7;quick+2=3
注意:
- 输入链表不能为空;
- k不大于链表长度;
class NodeList{
int val;
NodeList next = null;
NodeList(int val){
this.val = val;
}
}
public class Solution{
public ListNode FindKthTotail(ListNode head, int k){
# 链表不为空
if(k == 0 || head == null){
return null;
}
ListNode temp = head;
# 链表长度不小于 k-1,头结点已经验证过了
for(int i = 0; i < k-1; i++){
if(temp.next != null){
temp = temp.next;
}else{
return null;
}
}
ListNode quick = head;
ListNode slow = head;
#当 i < k-1 时,slow 指针动,quick 指针不动;
for(int i = 0; i < k-1; i++){
slow = slow.next;
}
while(slow.next!=null){
slow=slow.next;
quick=quick.next;
}
return quick;
}
}
网友评论