描述
输入一个链表,输出一个链表,该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。
如果该链表长度小于k,请返回一个长度为 0 的链表。
双指针法
- 用两个指针 left, right 指向头节点
- 把 right 指针后移 k 个位置
- 把 left, right 同时后移直到 right 到链表尾部,此时 left 指向的就是倒数第 k 个节点。
代码实现如下:
// c++
class Solution {
public:
ListNode* FindKthToTail(ListNode* pHead, int k) {
ListNode* r = pHead;
while (k-- && r)
r = r->next;
if (k >= 0) return nullptr; // 此时说明 k 比链表长度长
ListNode* l = pHead;
while (r)
r = r->next, l = l->next;
return l;
}
};
# python3
class Solution:
def FindKthToTail(self , p , k ):
l, r = p, p
while k > 0 and r:
r = r.next
k -= 1
if k > 0: return None
while r:
l = l.next
r = r.next
return l