题目描述:

• 输入一个链表，输出该链表中倒数第k个节点
• 为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点
• 举例:一个链表有6个节点，从头结点开始，它们的值依次是1、2、 3、 4、 5、 6。这个链表的倒数第三个节点是值为4的节点

题目解读

为了实现只遍历链表一次就能找到倒数第k节点，定义两个指针。
第一个指针从链表头指针开始遍历向前走k-1步，即到达第k个节点。此时第二个指针开始从链表的头指针开始遍历，这两个指针之间保持k-1个节点的距离。所以很容易想到若第一个指针到达链表的尾节点时，第二个指针正好指向倒数第k个节点(因为这两个指针刚好差k-1个节点的距离)

前期准备

• 创建节点

 struct ListNode{
        int val;
        struct ListNode *next;
        ListNode(int x) :val(x),next(NULL){}
   }

• 尾插法建立链表
  这里初始化节点值的方法用的是ListNode list=new ListNode(0),意思是初始化一个节点值为0的空节点

ListNode* create(){
                       ListNode *p,*head,*tail;
                      head = tail = NULL;
                       for(int i =0;i<7;i++){
                          p = new ListNode(i);
                          if(!head){
                              head = p;
                          }
                          else{
                            tail->next = p;
                          }
                          tail = p;
                       }
                       return head;
                  }

• 输出函数。从头结点开始遍历

void print_Node(ListNode *head){
                     while(head){
                        cout<<head->val<<" ";
                        head = head->next;
                     }
                     cout<<endl;
                }

核心代码

创建一个函数FindKthToTail，传入两个参数k和头结点pListHead。

• 为了增强代码的鲁棒性，首先判断头结点是否存在即链表是否为空并判断k值是否为0。
• 然后让第一个节点往前移动k-1步，此时应该判断链表长度小于k时应返回NULL
• 最后，用while循环遍历第一个节点，第二个节点也跟着移动。当第一个节点走到尾时，第二个节点刚好在倒数第k个位置

                ListNode* FindKthToTail(ListNode* pListHead,unsigned int k){
                         ListNode *qian = pListHead;
                         ListNode *hou = pListHead;
                         //如果链表为空或要求返回k=0的点，则返回NULL
                          if(!pListHead || !k){
                              return NULL;
                          }
                          // 往前走k-1步，如果链表长度小于k则返回NULL
                          for(int i =0;i<k-1;i++){
                             if(qian->next){
                               qian = qian->next;
                             }
                             else{
                                return NULL;
                             }
                          }
                          while(qian->next){
                                qian = qian->next;
                                hou = hou->next;
                          }
                          return hou;
                }

补充主函数

int main(){
      Solution ss;
       ListNode *head = NULL;
       ListNode *kth = NULL;
 
      head = ss.create();
       ss.print_Node(head);
      kth = ss.FindKthToTail(head,3);
       cout<<kth->val<<endl;
      return 0;
 }

参考