题目
输入一个链表,输出该链表中倒数第k个结点。
注意:
k >= 0;
如果k大于链表长度,则返回 NULL;
样例
输入:链表:1->2->3->4->5 ,k=2
输出:4

解法:模拟

首先求出链表的长度,如果k大于链表长度,则返回 NUL
再从头(0)开始遍历到第n-k个结点即可
时间复杂度O(n),空间复杂度O(1)

  1. /**
  2. * Definition for singly-linked list.
  3. * struct ListNode {
  4. * int val;
  5. * ListNode *next;
  6. * ListNode(int x) : val(x), next(NULL) {}
  7. * };
  8. */
  9. class Solution {
  10. public:
  11. ListNode* findKthToTail(ListNode* pListHead, int k) {
  12. if (k == 0) return nullptr;
  13. int len = 0;
  14. auto p = pListHead;
  15. while (p) {
  16. p = p->next;
  17. len++;
  18. }
  19. if (k > len) return nullptr;
  20. p = pListHead;
  21. k = len - k;
  22. while (k--) {
  23. p = p->next;
  24. }
  25. return p;
  26. }
  27. };