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

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

ListNode* FindKthToTail(ListNode* pHead, int k) {
      ListNode *fast_KStepNode = pHead;
      
      while(fast_KStepNode && k){
        fast_KStepNode = fast_KStepNode->next;
        k--;
      }
      
      while(fast_KStepNode){
        fast_KStepNode = fast_KStepNode->next;
        pHead = pHead->next;
      }
      
      return (k ? fast_KStepNode : pHead);
    }

# 2. 空间复杂度 O(n)，时间复杂度 O(n) - 有前面简单的方法就不优化这个复杂的方法了

ListNode* FindKthToTail(ListNode* pHead, int k) {
      /* 1.空间复杂度 O(n)，时间复杂度 O(n) */
      queue<ListNode*> Q;
      ListNode* Node = pHead;
      ListNode* returnNode = NULL;
      
      // 队列先存k个结点
      while(Q.size() < k){
        // 如果需要的k个结点没存完Node就到尾了
        // 则可以知道该链表长度 < k,返回一个长度为 0 的链表
        if (Node == NULL){ return returnNode; }
        Q.push(Node);
        Node = Node->next;
      }
      
      while(Node){
        Q.pop();
        Q.push(Node);
        Node = Node->next;
      }
      returnNode = Q.front();
      
      return returnNode;
    }