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

NC69 链表中倒数最后k个结点

题意：

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

1. 快慢指针法

题目是单链表，链表的倒数第k个节点再走k步恰好是尾结点，而尾结点可以用类似if (p->next)的语句判断，据此可以设计出如下思路：

• 定义两个指针，pStart和pEnd，初始化为头节点
• pEnd先走k步，然后pStart和pEnd同时往后走，直到pEnd碰到链表尾部。

以样例[1,2,3,4,5,6],k = 2为例， 如图所示：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        ListNode* pStart = pHead;
        ListNode* pEnd = pHead;

        int i = 0; // 记录下pEnd指针的移动步数

        // 注意这里wa了一次，有的样例k是大于链表总长度的，需要判断下k步是否走到链表尾部
        for (; i < k && pEnd; i++) pEnd = pEnd->next;

        // 如果k>链表总长度，说明倒数第k个节点无意义
        // 但是k=链表总长度的话，说明pStart即为答案，通过后面的while可以找出。
        if (k > i) return nullptr;

        // 快慢指针一起走
        while (pEnd) pStart = pStart->next, pEnd = pEnd->next;
        return pStart;        
    }
};

• 时间复杂度：设链表节点数为，总时间复杂度为, 先走k步，再走n-k步，共计为n步。
• 空间复杂度：

2. 使用栈解决

我们先把链表所有节点入栈，再出栈k次，每次出栈都串联到前面，就可以了。

同样注意一下 k >= 链表总长度的边界情况。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        stack<ListNode*> s;

        // 把链表所有节点入栈
        ListNode* pTemp = pHead;
        while (pTemp) {
            s.push(pTemp = pTemp->next);
        }

        // 特判k>=n
        if (k > s.size()) return nullptr;
        else if (k == s.size()) return pHead;

        // 把倒数第一个节点取出来
        ListNode* pStart = s.top();
        s.pop();

        // 迭代k次，注意倒数k个节点开始指向的链表共计k+1个点。
        while (k--) {
            pTemp = s.top();
            s.pop();

            pTemp->next = pStart;
            pStart = pTemp;
        }
        return pStart;
    }
};

• 时间复杂度：设链表节点数为，总时间复杂度为, 先迭代次把链表入栈，再弹栈次。
• 空间复杂度： O(n)，定义了大小为n的栈。