1.用快慢指针,快指针先走k步,然后两指针一起走,快指针到末尾时,慢指针刚好到倒数第k个位置。
2.仅用一个指针,先全部遍历求出结点总数n,然后让指针从头开始再次遍历,走n-k次即可到达倒数第k个位置。
方法一:
struct ListNode* FindKthToTail(struct ListNode* pHead, int k ) {
struct ListNode* fast = pHead;
struct ListNode* slow = pHead;
if(pHead == NULL)
return NULL;
while(fast != NULL && k > 0){
fast = fast->next;
k--;
}
if(k > 0)
return NULL;
while(fast!= NULL){
fast = fast->next;
slow = slow->next;
}
return slow;
}
方法二:
ListNode* FindKthToTail(ListNode* pHead, int k) {
ListNode* p = pHead;
int len=0;
while(p != NULL){
p=p->next;
len++;
}
if(len < k)
return NULL;
p = pHead; //回到头结点从头开始遍历
for(int i = 0; i < len-k; i++){
p = p->next;
}
return p;
}

京公网安备 11010502036488号