一、题目
输入一个链表,输出该链表中倒数第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); } |
测试结果:
评论