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

方法一：先遍历链表得到链表的节点数目，即可得到倒数最后K个节点是正数第几个节点。

时间复杂度：o(n)

空间复杂度：o(1)

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        //特殊情况处理；链表为空和k不大于0两种情况
        if (pHead == nullptr || k <= 0)
            return nullptr;

        ListNode* pnode = pHead;
        ListNode* temp = pHead;
        int length = 0;
	  	//得到链表长度
        while (pnode) {
            pnode = pnode->next;
            length++;
        }
	  	//如果k大于链表长度，返回nullptr
        if (k > length) {
            return nullptr;
        } else {
            for(int i = 0; i < length - k; i++) {
                temp = temp->next;
            }
            return temp;
        }
    }
};

方法二：双指针求解

设置两个指针都等于头结点，一个指针先走k步；然后两个指针同时移动，当快指针指向nullptr，慢指针到达倒数第k个节点。

时间复杂度：o(n)

空间复杂度：o(1)

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
	  	//特殊情况处理；链表为空和k不大于0两种情况
        if (pHead == nullptr || k <= 0)
            return nullptr;

        ListNode* slow = pHead;
        ListNode* fast = pHead;
		//快指针移动K位
        for (int i = 0; i < k; i++) {
            if (fast == nullptr)
                return nullptr;
            else
                fast = fast->next;
        }
	  	//两个指针同时移动直到快指针指向到达链表尾部
        while (fast) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

方法三：使用栈求解。利用栈先进后出的特点，倒数第K个节点即是第K个出栈的节点。

时间复杂度：o(n)

空间复杂度：o(n)

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
	  	//特殊情况处理；链表为空和k不大于0两种情况
        if (pHead == nullptr || k < 0)
            return nullptr;

        stack<ListNode*> sk;
        ListNode* pnode = pHead;
        while(pnode != nullptr) {
            sk.push(pnode);
            pnode = pnode->next;
        } 
	  	//如果K大于链表数目
        if (k > sk.size()) {
            return nullptr;
        } else {
            while(k-1) {
                sk.pop();
                k--;
            }
            return sk.top();
        }
    }
};