题目描述

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

题目解读

• 剑指Offer 134
• 为了实现只遍历链表一次就能找到倒数第 k 节点，我们可以定义两个指针。第一个指针从链表的头指针开始遍历向前走 k-1 步，第二个指针保持不动；从第 k 步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在 k-1，当第一个(走在前面的)指针到达链表的尾节点时，第二个(走在后面的)指针正好指向倒数第 k 个节点

代码

• 第一轮代码

#include<iostream>
using namespace std;

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

class Solution {
public:
    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;
    }

    ListNode* create(){
        ListNode *p;
        ListNode *head = NULL;
        ListNode *tail = NULL;

        for(int i=1; i <= 6; 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;
    }
};

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;
}

• 第二轮代码

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        ListNode *qian = pListHead;
        ListNode *hou  = pListHead;
        
        if(pListHead == NULL || k == 0){
            return NULL;
        }
        
        for(int i=0; i < k-1; i++){
            qian = qian->next;
            if(qian == NULL){
                return NULL;
            }
        }
        
        while(qian->next){
            qian = qian->next;
            hou = hou->next;
        }
        return hou;
    }
};

总结展望

• 题目思路很新颖，值得好好学习
• 通过这道题更加深刻的了解到代码鲁棒性的重要性，正如书中所提到的下述三种特殊情况是否注意到并且在程序中一一解决，很重要..
  • 1, 输如链表为空
  • 2, 链表节点数小于k
  • 3, 输入参数 k = 0

相关题目

• 求链表的中间节点。如果链表中的节点总数为奇数，则返回中间节点；如果链表的节点总数为偶数，则返回中间节点两个节点中的任意一个。
• 为了解决这个问题，我们也可以定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。当走得快的指针走到链表的末尾时，走得慢的指针正好在链表的中间。