剑指22：链表中倒数第k个节点

传送门

nowcoder
leetcode

题目描述

输入一个链表，输出该链表中倒数第k个结点。

C++ 代码 - nowcoder

/*
    第一次遍历：求出链表的长度
    第二次遍历：
        倒数第 k 个节点，即为正数第 n - k + 1个节点。
        第一个节点开始走 n - k 步，位于倒数第 k 个节点。

    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        ListNode* p = pListHead;
        int length = 0;
        while (p != nullptr) {
            length ++;
            p = p->next;
        }

        length = length - k;
        if (length < 0) return nullptr;
        p = pListHead;
        while (length != 0) {
            length --;
            p = p->next;
        }
        return p;
    }
};

/*
    双指针，遍历一次
    设链表节点数为 n，求倒数第 k 个节点。
    倒数第 k 个节点，就是正数第 n - k + 1 个节点。
    
    1. 设置两个指针 fast、slow
    2. 先让 fast 走 k 个节点(一次一步)，走到第 k + 1 个节点；
    3. 然后 fast 和 slow 同时走(一次一步)，直到 fast 为空。
    fast 走过的距离为 n - k；
    slow 走了 n - k，走到了 n - k + 1 个节点。

    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        ListNode *slow = pListHead, *fast = pListHead;
        while (k != 0) {
            k --;
            // 判断是否 k 大于链表总长度
            if (fast != nullptr)
                fast = fast->next;
            else
                return nullptr;
        }

        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

C++ 代码 - leetcode

/*
    第一次遍历：求出链表的长度
    第二次遍历：
        倒数第 k 个节点，即为正数第 n - k + 1个节点。
        第一个节点开始走 n - k 步，位于倒数第 k 个节点。
*/
class Solution {
public:
    ListNode* trainingPlan(ListNode* head, int k) {
        int length = 0;
        ListNode* p = head;
        while (p != nullptr) {
            length ++;
            p = p->next;
        }

        length = length - k;
        if (length < 0) return nullptr;
        p = head;
        while (length != 0) {
            length --;
            p = p->next;
        }
        return p;
    }
};

/*
    双指针，遍历一次
    设链表节点数为 n，求倒数第 k 个节点。
    倒数第 k 个节点，就是正数第 n - k + 1 个节点。
*/
class Solution {
public:
    ListNode* trainingPlan(ListNode* head, int k) {
        ListNode *slow = head, *fast = head;
        while (k != 0) {
            k --;
            if (fast != nullptr)
                fast = fast->next;
            else
                return nullptr;
        }

        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};