1.一种较笨的办法是先将链表元素入栈,然后出栈找到倒数第k个节点值,再拿着值遍历链表去找到对于节点。

  • 时间复杂度:O(n) (3n 遍历-出栈-遍历)
  • 空间复杂度:O(n) (一个栈)

2.快慢指针,要注意边界值的处理。

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)只额外需要一个指针的空间。
 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
12         //边界判断!!!
13         if(pListHead == nullptr || k == 0)
14             return nullptr;
15         auto p = pListHead;
16         //快先走k-1
17         for(int i=0; i<k-1; i++)
18         {
19             if(p->next == nullptr)
20                 return nullptr;
21             else
22                 p = p->next;
23         }
24         //一起走到尾
25         while(p->next != nullptr)
26         {
27             p = p->next;
28             pListHead = pListHead->next;
29         }
30         return pListHead;
31     }
32 };