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