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; }