《剑指offer》面试题22：链表中的倒数第k个节点

马谦马谦马谦

615
文章

17
评论

2020年2月9日19:22:16数据结构和算法评论198字数 662阅读2分12秒阅读模式

一、题目

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

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

《剑指offer》面试题22：链表中的倒数第k个节点-图片1

二、解题思路

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

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

《剑指offer》面试题22：链表中的倒数第k个节点-图片2

fast指针先往前走三步：

《剑指offer》面试题22：链表中的倒数第k个节点-图片3

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

《剑指offer》面试题22：链表中的倒数第k个节点-图片4

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

三、代码

代码中需要注意的问题：

链表可能为空，避免空指针访问。
链表长度可能不够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;
}

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个元素。

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

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

// 案例：获取倒数第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, 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);
}