怎么给自己建网站,大同网站建设开发,百度推广一级代理商名单,wordpress商业用途本篇文章将为大家讲解一道关于链表的经典题目——求两个链表的共同后缀节点。该问题在实际开发中同样具有很大的应用价值#xff0c;是每一位数据结构学习者不可错过的重要题目。
问题描述
假设我们有一个带头结点的单链表来保存单词#xff0c;每个节点包含一个字符和指向…本篇文章将为大家讲解一道关于链表的经典题目——求两个链表的共同后缀节点。该问题在实际开发中同样具有很大的应用价值是每一位数据结构学习者不可错过的重要题目。
问题描述
假设我们有一个带头结点的单链表来保存单词每个节点包含一个字符和指向下一个节点的指针。若两个单词的后缀相同它们可以共享相同的后缀存储空间。例如
单词loading 和 being 有相同的后缀 ing可以共享存储。
题目要求
设 str1 和 str2 分别指向两个单词所在链表的头节点请设计一个尽可能高效的算法找出两个链表共同后缀的起始位置。
要求
给出算法的设计思想。使用 C 代码实现算法并在关键部分给出注释。分析算法的时间复杂度。
设计思路
1. 暴力匹配法
最直接的思路是将链表 str1 的每一个节点依次与链表 str2 的节点进行匹配如果匹配到相同的节点则继续向后比较直到找到第一个完全相同的后缀位置。
实现步骤
从链表 str1 开始的每个节点分别与 str2 中的节点开始逐一匹配。若匹配的节点数据相同继续匹配下一个节点若不相同则跳到下一个节点。当匹配到第一个后缀起始点时返回该节点位置。
#include bits/stdc.husing 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;
}代码结构分析 search 函数这是主函数它通过双层循环在链表 first 和 second 中查找共同后缀的起始位置。 外层循环遍历链表 first 的每个节点 x。内层循环对于每个节点 x遍历链表 second 的每个节点 y。 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 × n × k ) ≈ O ( n 3 ) O(m \times n \times k) \approx O(n^3) O(m×n×k)≈O(n3)
2. 双指针法
考虑一种更为高效的 双指针法。
思路
我们先遍历两个链表得到它们的长度差 d。然后让较长的链表先走 d 步这样两个链表剩下的节点数相等。之后同时遍历两个链表直到找到第一个相同的节点即为共同后缀的起始位置。
实现步骤
计算两个链表的长度 len1 和 len2求得它们的长度差 d。将较长的链表向前移动 d 步。同时遍历两个链表直到找到第一个相同的节点。
优点通过两次遍历计算长度 查找共同节点时间复杂度降低到 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 长。如果直接从头开始同时遍历两个链表由于长度不相等较长链表的指针会先到达结尾而我们需要两个链表在“对齐的起始位置”进行比较。
因此为了让两个链表末尾部分对齐
让较长的链表先移动 |x - y| 步。这样移动后两个链表的剩余部分长度相等。从这个新位置开始两个链表的指针将同步向后遍历确保同时到达链表的末尾。 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表示没有共同后缀。
算法时间复杂度分析 计算长度 函数 getLength 分别计算链表 n 和 m 的长度耗时为 (O(m)) 和 (O(n))。 对齐链表长度 假设 str1 比 str2 长。为了让两个链表的尾端对齐较长的链表 str1 向前移动 |m - n| 步。无论如何对齐过程的时间复杂度是 (O(|m - n|))这可以简化为 (O(m n))。 寻找共同后缀 接下来两个链表同时从对齐位置向后遍历寻找第一个相同的节点。这部分的时间复杂度为 O ( m i n ( m , n ) ) O(min(m, n)) O(min(m,n))但可以包含在 O ( m i n ( m , n ) ) O(min(m, n)) O(min(m,n))的上界内。
因此整个算法的时间复杂度为 O ( m i n ( m , n ) ) O(min(m, n)) O(min(m,n))这涵盖了所有操作的最坏情况时间复杂度。这种算法之所以更高效是因为它只需要遍历每个链表最多两次。
结语
双指针法通过巧妙地同步遍历来提高效率非常适合此类链表问题。在链表题目中理解如何通过双指针控制遍历过程可以显著提升算法的效率。希望这篇文章能够帮助大家更好地理解链表的双指针技巧。
