题解 | 链表中倒数最后k个结点

描述

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

数组法

把每个节点装进数组中，访问倒数第 k 个元素。

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        vector<ListNode*> res;
        for (; pHead; pHead = pHead->next)
            res.emplace_back(pHead); // 把每个节点指针放入数组
        if (k > res.size() || !k) return nullptr; // 判断非法的 k 值
        return res[res.size() - k];
    }
};

python可以通过复数下标直接访问倒数第 k 个元素。

# python3
class Solution:
    def FindKthToTail(self , p , k ):
        res = []
        while p:
            res.append(p)
            p = p.next
        if k > len(res) or not k: return None # 判断非法的 k 值
        return res[-k]

两种方法都遍历了一次链表，所以时间复杂度是 O(n)，因为使用了一个数组空间复杂度是 O(n)。

双指针法

1. 用两个指针 left, right 指向头节点
2. 把 right 指针后移 k 个位置
3. 把 left, right 同时后移直到 right 到链表尾部，此时 left 指向的就是倒数第 k 个节点。
   
   代码实现如下：

   // c++
   class Solution {
   public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        ListNode* r = pHead;
        while (k-- && r) 
            r = r->next; // 移动右侧指针造成 k 的距离差
        if (k >= 0) return nullptr; // 此时说明 k 比链表长度长
        ListNode* l = pHead;
        while (r)
            r = r->next, l = l->next; // 两个指针一起移动找到倒数第 k 个节点
        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 // 判断不合法的 k 值
        while r:
            l = l.next
            r = r.next
        return l

   时间复杂度 O(n)，空间复杂度 O(1)。