一、题目

输入一个链表，输出该链表中倒数第k个节点，为了符合大多数人的习惯，k的序号从1开始，即链表的尾结点是倒数第一个节点。

例如，如下链表中的倒数第3个节点是3：

二、解题思路

使用快慢指针，快指针先走n步，然后快慢指针同时走，直到快指针为null，慢指针就是倒数第n个节点。

以上面的链表为例，初始时，两个指针都指向链表开头：

fast指针先往前走三步：

此时，fast和slow同时往前走，直到fast为空：

此时slow所在的位置刚好就是倒数第三个节点。

三、代码

代码中需要注意的问题：

1. 链表可能为空，避免空指针访问。
2. 链表长度可能不够n，遍历fast的时候注意判断非空，并且外部应该判断出这一点。

list_node *find_kth_to_tail(list_node *head, int n) {
    list_node *slow, *fast;
    
    // [1] 注意链表为空的情况
    if (head == nullptr)
        return nullptr;

    fast = head;
    slow = head;

    // [2] fast指针先走n步
    while (fast && n--) {
        fast = fast->next;
    }

    // [3] 整个链表长度不够n
    if (!fast && n > 0)
        return nullptr;

    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }

    return slow;
}

四、单元测试

单元测试主要覆盖以下几点：

1. 链表为空的场景。
2. 链表不为空，获取倒数第1个节点。
3. 链表不为空，获取倒数第n个节点，n等于链表长度。
4. 链表不为空，获取倒数第n个节点，n大于链表长度。

TestFixtures定义了三个链表，第一个链表有5个元素，第二个链表为空，第三个链表有1个元素。

class list_test : public ::testing::Test {
protected:
    void SetUp() override {
        int i, arr[] = {2, 3, 4, 5};
        // 初始化链表1
        list_node *p;
        p = new list_node{1, nullptr};
        list1 = p;
        for (i = 0; i < 4; i++) {
            p->next = new list_node{arr[i], nullptr};
            p = p->next;
        }
        // 初始化链表2
        list2 = nullptr;
        // 初始化链表3
        list3 = new list_node{1, nullptr};
    }

    // 释放链表节点
    void TearDown() override {
        list_node *p, *next;
        p = list1;
        while (p) {
            next = p->next;
            delete p;
            p = next;
        }
        delete list3;
        list3 = nullptr;
    }

    // 初始化三个链表，第一个链表有5个节点，第二个链表为空，第三个链表只有一个节点
    list_node *list1;
    list_node *list2;
    list_node *list3;
};

测试案例一：获取倒数第n个节点，n分别大于、小于和等于链表长度。

// 案例：获取倒数第n个节点，n小于链表长度
TEST_F(list_test, multi_node) {
    list_node *p;
    // 倒数第一个节点
    p = find_kth_to_tail(list1, 1);
    EXPECT_EQ(p->data, 5);
    // 倒数第二个节点
    p = find_kth_to_tail(list1, 2);
    EXPECT_EQ(p->data, 4);
    // 倒数第三个节点
    p = find_kth_to_tail(list1, 3);
    EXPECT_EQ(p->data, 3);
    // 倒数第四个节点
    p = find_kth_to_tail(list1, 4);
    EXPECT_EQ(p->data, 2);
    // 倒数第五个节点
    p = find_kth_to_tail(list1, 5);
    EXPECT_EQ(p->data, 1);
    // 倒数第六个节点 --> 空
    p = find_kth_to_tail(list1, 6);
    EXPECT_FALSE(p);
}

测试案例二：测试空链表。

// 案例：空链表测试
TEST_F(list_test, no_node) {
    list_node *p;
    p = find_kth_to_tail(list2, 1);
    EXPECT_FALSE(p);
    p = find_kth_to_tail(list2, 2);
    EXPECT_FALSE(p);
}

测试案例三：只有一个节点的链表测试。

// 案例：只有一个节点的链表测试
TEST_F(list_test, one_node) {
    list_node *p;
    // 倒数第一个节点，不为空
    p = find_kth_to_tail(list3, 1);
    EXPECT_EQ(p->data, 1);
    // 倒数第二个节点，空
    p = find_kth_to_tail(list3, 2);
    EXPECT_FALSE(p);
    // 倒数第三个节点，空
    p = find_kth_to_tail(list3, 3);
    EXPECT_FALSE(p);
}

测试结果：