1、快慢指针:时间复杂度是O(n),空间复杂度O(1)
思路:快指针比慢指针多走K步,当快指针走完时,慢指针正好是倒数第K个
public ListNode FindKthToTail (ListNode pHead, int k) {
if(pHead==null){
return null;
}
ListNode slow = pHead;
ListNode fast = pHead;
while(fast!=null&&k>0){
fast=fast.next;
k--;
}
if(k>0){
return null;
}
while(fast!=null){
slow=slow.next;
fast=fast.next;
}
return slow;
}
2、统计链表长度:时间复杂度是O(n),空间复杂度O(1)
思路:通过统计链表的长度,计算倒数第K个是正数第几个,遍历链表到当前位置停下来。
public ListNode FindKthToTail (ListNode pHead, int k) {
// write code here
int s = 0;
//统计链表长度
ListNode node = pHead;
while(node!=null){
node=node.next;
s++;
}
if(s<k){
return null;
}
//计算是第几个停下来
int target = s-k;
s=0;
while(s<target){
pHead = pHead.next;
s++;
}
return pHead;
}

京公网安备 11010502036488号