【每日一题】2012考研数据结构 - 求字符串链表公共后缀

本篇文章将为大家讲解一道关于链表的经典题目——求两个链表的共同后缀节点。该问题在实际开发中同样具有很大的应用价值，是每一位数据结构学习者不可错过的重要题目。

问题描述

假设我们有一个带头结点的单链表来保存单词，每个节点包含一个字符和指向下一个节点的指针。若两个单词的后缀相同，它们可以共享相同的后缀存储空间。例如：

• 单词loading 和 being 有相同的后缀 ing，可以共享存储。

题目要求

设 str1 和 str2 分别指向两个单词所在链表的头节点，请设计一个尽可能高效的算法，找出两个链表共同后缀的起始位置。

要求：

1. 给出算法的设计思想。
2. 使用 C++ 代码实现算法，并在关键部分给出注释。
3. 分析算法的时间复杂度。

设计思路

1. 暴力匹配法

最直接的思路是将链表 str1 的每一个节点依次与链表 str2 的节点进行匹配，如果匹配到相同的节点，则继续向后比较，直到找到第一个完全相同的后缀位置。

实现步骤：

1. 从链表 str1 开始的每个节点，分别与 str2 中的节点开始逐一匹配。
2. 若匹配的节点数据相同，继续匹配下一个节点；若不相同则跳到下一个节点。
3. 当匹配到第一个后缀起始点时，返回该节点位置。

#include "bits/stdc++.h"using namespace std;struct Node{int value;Node* next;
};bool check(Node* first, Node* second) {Node* l = first;Node* r = second;while(l != nullptr && r != nullptr) {if(l -> value != r ->value) return false;l = l -> next;r = r -> next;}return l  == nullptr &&  r  == nullptr;
}Node* search(Node* first, Node* second) {Node* x = first;while(x != nullptr ) {Node*  y = second;while(y != nullptr) {if(x -> value == y -> value && check(x, y)) {return x;}y = y -> next;}x = x -> next;}return nullptr;
}int main() {Node* common = new Node{'i', new Node{'n', new Node{'g', nullptr}}};// 创建两个测试链表Node* str1 = new Node{ 'l', nullptr };str1->next = new Node{ 'o', nullptr };str1->next->next = new Node{ 'a', nullptr };str1->next->next->next = new Node{ 'd', nullptr };str1->next->next->next->next = common;Node* str2 = new Node{ 'b', nullptr };str2->next = new Node{ 'e', nullptr };str2->next->next = common; // 共享后缀部分// 查找共同后缀的起始位置Node* result = search(str1, str2);if (result != nullptr) {cout << "共同后缀的起始位置: " << (char)result->value << endl;} else {cout << "没有共同后缀" << endl;}return 0;
}

代码结构分析

1. search 函数：这是主函数，它通过双层循环在链表 first 和 second 中查找共同后缀的起始位置。

   • 外层循环：遍历链表 first 的每个节点 x。
   • 内层循环：对于每个节点 x，遍历链表 second 的每个节点 y。

2. check 函数：search 函数在 if(x -> value == y -> value && check(x, y)) 中调用 check 函数，用于比较链表 first 从节点 x 开始的后缀和链表 second 从节点 y 开始的后缀。

   • check 函数的时间复杂度为 (O(n))，因为它从两个节点开始逐一比较剩下的所有节点。

时间复杂度计算

• 外层循环遍历链表 first 的每个节点，时间复杂度为 (O(m))（m 是链表 first 的长度）。
• 内层循环遍历链表 second 的每个节点，时间复杂度为 (O(n))（n 是链表 second 的长度）。
• check 函数的复杂度为 (O(k))，其中 k 是 x 和 y 之后的节点数量，最多接近 O(max(m, n))。

因此，整体时间复杂度为：$O(m\times n\times k)\approx O(n^3)$

2. 双指针法

考虑一种更为高效的 双指针法。

思路

我们先遍历两个链表，得到它们的长度差 d。然后让较长的链表先走 d 步，这样两个链表剩下的节点数相等。之后同时遍历两个链表，直到找到第一个相同的节点，即为共同后缀的起始位置。

实现步骤

1. 计算两个链表的长度 len1 和 len2，求得它们的长度差 d。
2. 将较长的链表向前移动 d 步。
3. 同时遍历两个链表，直到找到第一个相同的节点。

优点：通过两次遍历（计算长度 + 查找共同节点），时间复杂度降低到 O(m + n)。

C++ 实现代码

以下是使用 C++ 实现的双指针法代码：

#include "bits/stdc++.h"
using namespace std;struct Node{int value;Node* next;
}; // 计算链表长度
int getLength(Node* node) {int length = 0;while(node != nullptr) {length++;node = node -> next;}return length;
}// 查找共同后缀起始节点
Node* search(Node* n, Node* m) {int len1 = getLength(n);int len2 = getLength(m);// 长链表先走 |len1 - len2| 步while(len1 > len2) {len1--;n = n -> next;}while(len2 > len1) {len2--;m = m -> next;}// 双指针同时遍历寻找共同节点while(n != nullptr && m != nullptr) {if(n == m ) return n;n = n -> next;m = m -> next;}return nullptr;
}int main() {Node* common = new Node{'i', new Node{'n', new Node{'g', nullptr}}};Node* str1 = new Node{ 'l', nullptr };str1->next = new Node{ 'o', nullptr };str1->next->next = new Node{ 'a', nullptr };str1->next->next->next = new Node{ 'd', nullptr };str1->next->next->next->next = common;Node* str2 = new Node{ 'b', nullptr };str2->next = new Node{ 'e', nullptr };str2->next->next = common;Node* result = search(str1, str2);if (result != nullptr) {cout << "共同后缀的起始位置: " << (char)result->value << endl;} else {cout << "没有共同后缀" << endl;}return 0;
}

这段代码的核心思想是通过调整两个链表的起始位置，使得它们在同一个位置开始比较，以便找到第一个相同的节点作为共同后缀的起始点。以下是逐步的代码讲解，特别是对为什么较长的链表需要先移动几步的解释。

代码分解与讲解

#include "bits/stdc++.h"
using namespace std;struct Node{int value;Node* next;
}; 

• 这里定义了链表节点的结构体 Node，包含一个整型数据 value 和一个指向下一个节点的指针 next。

int getLength(Node* node) {int length = 0;while(node != nullptr) {length++;node = node -> next;}return length;
}

• getLength 函数用于计算链表的长度。它遍历链表并计数，直到链表末尾。时间复杂度为 (O(n))，其中 (n) 是链表的长度。

Node* search(Node* n, Node* m) {int x = getLength(n);int y = getLength(m);

• search 函数是主函数，用来找到两个链表的共同后缀。首先调用 getLength 获取链表 n 和 m 的长度，分别记为 x 和 y。

为什么较长的链表要先移动？

假设链表 n 比链表 m 长。如果直接从头开始同时遍历两个链表，由于长度不相等，较长链表的指针会先到达结尾，而我们需要两个链表在“对齐的起始位置”进行比较。

因此，为了让两个链表末尾部分对齐：

1. 让较长的链表先移动 |x - y| 步。这样移动后，两个链表的剩余部分长度相等。
2. 从这个新位置开始，两个链表的指针将同步向后遍历，确保同时到达链表的末尾。

    while(x > y) {x--;n = n -> next;} while(y > x) {y--;m = m -> next;}

• 在这里，较长的链表会先移动 |x - y| 步，以确保后续同步遍历时，两链表末尾部分的节点数相同。

    while(n != nullptr && m != nullptr) {if(n == m) return n;n = n -> next;m = m -> next;}return nullptr;
}

• 现在，两个链表 n 和 m 同时从新的位置开始遍历。
• 如果发现 n 和 m 指向同一个节点（即它们有相同的地址），则该节点即为第一个公共节点，返回该节点。
• 如果遍历结束未找到公共节点，则返回 nullptr，表示没有共同后缀。

算法时间复杂度分析

1. 计算长度：

   • 函数 getLength 分别计算链表 n 和 m 的长度，耗时为 (O(m)) 和 (O(n))。

2. 对齐链表长度：

   • 假设 str1 比 str2 长。为了让两个链表的尾端对齐，较长的链表 str1 向前移动 |m - n| 步。无论如何，对齐过程的时间复杂度是 (O(|m - n|))，这可以简化为 (O(m + n))。

3. 寻找共同后缀：

   • 接下来，两个链表同时从对齐位置向后遍历，寻找第一个相同的节点。这部分的时间复杂度为 $O(min(m,n))$，但可以包含在 $O(min(m,n))$的上界内。

因此，整个算法的时间复杂度为 $O(min(m,n))$，这涵盖了所有操作的最坏情况时间复杂度。这种算法之所以更高效，是因为它只需要遍历每个链表最多两次。

结语

双指针法通过巧妙地同步遍历来提高效率，非常适合此类链表问题。在链表题目中，理解如何通过双指针控制遍历过程，可以显著提升算法的效率。希望这篇文章能够帮助大家更好地理解链表的双指针技巧。