Icoding题解线性表倒数查找

题干

链表倒数查找

已知一个带有表头结点的单链表, 假设链表只给出了头指针L。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。
函数原型为：int lnk_search(LinkList L, int k, ElemType* p_ele)
若查找成功，函数通过指针参数 p_ele 返回该结点 data 域的值，此时函数返回 1；否则，函数返回 0。相关定义如下：

struct _lnklist{
    ElemType data;
    struct _lnklist *next;
};

typedef struct _lnklist Node;
typedef struct _lnklist *LinkList;

分析

简要分析题干：
题目的要求是，查找链表中倒数第k个位置的结点，算法尽量高效，即我们需要尽可能减少时间复杂度。
结构体已经确定，因此我们无法通过改变链表结构体的内容（譬如增加一个新的域，将其变换为双向链表），来使得操作更加简单。
应当注意的问题：
1. 单链表操作
2. 头结点为空
3. 寻找倒数第k个结点（实现搜索）
4. 使得算法尽量高效
解题思路：
这里给出一个算法，其时间复杂度会在 O(n) 。即正常遍历链表，直到遍历到倒数第 k 个结点。
1. 首先，我们需要知道链表的长度 n。
2. 根据 n，我们可以得到 n - k + 1 是我们需要走过的结点数量。关键在于理解这一步，为什么从头结点开始的步数是 n - k + 1 ？自己举例尝试即可验证。
3. 假设 k 大于 n , 搜索失败，函数返回0，否则返回1。

核心代码

首先，我们设置一个临时的指针遍历链表，用于记录链表的结点数量，然后用一个循环得到结点数量，此处n最终的值是链表的结点数。

LinkList Temp = L->next;
int n = 0;

while (Temp->next) {
    Temp = Temp->next;
    n++;
}

/*
加一个条件判断。
如果k大于n，即超出了链表结点数，查找就不可能成功。
直接返回0退出函数即可。
*/
if (k > n) {
    return 0;
}

在这里，我们已知一共需要走count步，每走一步count减1，count为0时退出循环，Temp的指向恰好是我们寻找到的那个结点

// 用一个变量储存我们需要走的步数（从头结点开始）
int count = n - k + 1;
// 刚刚设置的临时指针更新到头结点处，准备开始遍历链表
Temp = L;

while (count) {
    Temp = Temp->next;
    count--;
}

最后不要忘记赋值 p_ele 变量。
1
2
*p_ele = temp->data;
return 1;

完整代码

注意，完整代码在实现上稍微和前面的核心代码解释有出入，但运用的思想是完全相同的，不妨比较一下两者的差别在什么地方，此处差别有助于你理解 $n - k + 1$ 的本质。


int lnk_search(LinkList L, int k, ElemType* p_ele) {
    int n = 0;
    int count = 1;
    LinkList temp = L;
    while (temp->next != NULL)
    {
        temp = temp->next;
        n++;
    }
    
    if (k > n)
        return 0;
    
    k = n - k + 1;
    temp = L->next;
    while (count != k)
    {
        temp = temp->next;
        count ++;
    }
    
    *p_ele = temp->data;
    return 1;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。

Icoding题解 线性表 倒数查找

题干

分析

核心代码

完整代码

Icoding题解线性表倒数查找