【2024考研】题解7 | #链表中倒数最后k个结点#

/**（傻逼题）尾指针一直倒数着
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        ListNode *tail = pHead;//尾指针
        ListNode *ptail = pHead;//间断指针
        int length = 0;
	  //测量链表长度
        while(tail){
            tail = tail->next;
            length++;
        }
	  //测试输出
	  // cout<<"长度："<<length<<endl;
	  //我没k，k大于链表长度的情况
        if(k>length) return nullptr;
	  //时间（链表尾巴）一直倒数着
        for(int i = 0; i < length-k; i++){
            ptail = ptail->next;
        }
        return ptail;
    }
};
/*
GPT总结的傻逼题：
时间复杂度：O(n)，其中n为链表的长度。算法遍历了一次链表来计算链表的长度，然后再遍历一次链表来找到倒数第k个节点，所以时间复杂度为O(n)。

空间复杂度：O(1)，算法只使用了常数个额外的指针变量来辅助遍历链表，没有使用额外的数据结构，所以空间复杂度为O(1)。

算法思想：首先遍历链表一次，计算链表的长度。然后再遍历链表一次，找到倒数第k个节点。为了找到倒数第k个节点，可以使用两个指针，一个先走k-1步，然后两个指针一起向后移动，直到第一个指针到达链表末尾，此时第二个指针指向的就是倒数第k个节点。
*/