数据结构3：链表的运用和循环链表

数据结构3：链表的运用

写在前面：

链表是数据结构中很重要的一个，为此，我会单开一个章节来记录链表的使用，请不要好高骛远。

例题一：倒数定位

假设该链表只给出了头指针S。在不改变链表的前提下，请设计一个尽可能高效
的算法，查找链表中倒数第k个位置上的结点（k为正整数)。若查找成功，算法输出
该节点的data域的值，并返回1；否则，只返回0。

值得注意的是，如果我们一直遍历到链表的末尾，再掉头，无疑会导致极高的时间复杂度。所以

，我们会使用快慢指针的速度差来表示k。比如，k == 3，那么，我们设定两个指针Fast和slow，让Fast先走三步，slow再开始走，那么，当Fast走到最后（Fast指针指向空指针）时，slow的位置就是Fast往前三步的节点。

image-20250404165404424

所以，具体的代码实现是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int findNodeFS(Node *L, int k)
{
    Node *fast = L->next;
    Node *slow = L->next;
    for (int i = 0; i < k; i++)
    {
        fast = fast->next;
    }
    while(fast != NULL)
    {
        fast = fast->next;
        slow = slow->next;
    }
    printf("倒数第%d个节点值为：%d\n", k, slow->data);
    return 1; // 查找成功返回1
}

例题二：共同后缀

假定采用带头节点的单链表保存单词，当两个单问有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。

image-20250404200046663

设str1和str2分别指向两个单词所在单链表的头节点，请没计一个时间上尽可能高效的算法，找出由Sr1和str2所指向两个链表共同后缀的起
始位置（如图字符i所在结点的位置p)。

这里用哈希表可能更好，但是我还没学到。

所以，每个链表都有一个相同的后缀，后缀的长度是一定的，所以，我们获取两个链表的长度，他们之差就是后缀的长度，再用快慢指针就可以定位到共同后缀的第一个字母了。

image-20250404220225054

例题三：绝对值替换

用单链表保存 n 个整数，现要求设计一个时间复杂度尽可能高效的算法，对于链表中 data 的绝对值相等的节点，仅保留第一次出现的节点而删除其余绝对值相等的结点。

我们可以设置一个长度大于n+1（n个整数加上一个数据域为空的头节点就是n+1）的数组a，并将其初始化为0。然后，遍历整个链表，设置条件判断（这里说的date都是实际链表中的数据域的绝对值）：如果a[date]==0,将其设置为1，如果a[date] == 1，说明该date已经出现过了，就删除该节点，这就实现了ACM中类似的打表操作。遍历到末尾时，执行完毕。

image-20250404220211050

例题四：反转链表

给你一个单链表，要求你反转链表方向。

首先，我们需要三个指针，指针first指向NULL，指针Second指向头节点，指针Three指向头节点之后的一个节点，然后，只要Second的指针域不为空指针，将Second的指针域指向first，然后将first指向second，将second指向three，黑体操作就实现了操作器的移动。直到末尾，我们的反转工作就完成了。

image-20250404220627277

循环链表

循环链表（Circular Linked List）是另一种形式的链式存储结构。其特点是表
中最后一个节点的指针域指向头节点，整个链表形成一个环。

循环链表的判别条件是：P-> != HEAD

但是实际使用中往往不是纯的环，可以是这样的结构：

image-20250404224200811