一、题目
输入一个链表，输出该链表中倒数第 k 个节点，为了符合大多数人的习惯，k 的序号从 1 开始，即链表的尾结点是倒数第一个节点。
例如，如下链表中的倒数第 3 个节点是 3：
二、解题思路
使用快慢指针，快指针先走 n 步，然后快慢指针同时走，直到快指针为 null，慢指针就是倒数第 n 个节点。
以上面的链表为例，初始时，两个指针都指向链表开头：
fast 指针先往前走三步：
此时，fast 和 slow 同时往前走，直到 fast 为空：
此时 slow 所在的位置刚好就是倒数第三个节点。
三、代码
代码中需要注意的问题：
- 链表可能为空，避免空指针访问。
- 链表长度可能不够 n，遍历 fast 的时候注意判断非空，并且外部应该判断出这一点。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
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 个节点。
- 链表不为空，获取倒数第 n 个节点，n 等于链表长度。
- 链表不为空，获取倒数第 n 个节点，n 大于链表长度。
TestFixtures 定义了三个链表，第一个链表有 5 个元素，第二个链表为空，第三个链表有 1 个元素。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
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 分别大于、小于和等于链表长度。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// 案例：获取倒数第 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); } |
测试案例二：测试空链表。
|
1 2 3 4 5 6 7 8 |
// 案例：空链表测试 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); } |
测试案例三：只有一个节点的链表测试。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// 案例：只有一个节点的链表测试 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); } |
测试结果：
