链表中倒数最后k个结点

描述

输入一个链表,输出一个链表,该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。
如果该链表长度小于k,请返回一个长度为 0 的链表。

双指针法

  1. 用两个指针 left, right 指向头节点
  2. 把 right 指针后移 k 个位置
  3. 把 left, right 同时后移直到 right 到链表尾部,此时 left 指向的就是倒数第 k 个节点。
    链表中倒数最后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

链表中倒数最后k个结点

上一篇:机器学习——最优化问题:拉格朗日乘子法、KKT条件以及对偶问题


下一篇:This指向