当前位置：首页 > article >正文

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

article 2024/11/8 7:31:33

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

问题描述

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

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

题目要求

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

要求：

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

设计思路

1. 暴力匹配法

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

实现步骤：

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

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

代码结构分析

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))。

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

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 (min (m, n))$ ，但可以包含在 $O (min (m, n))$ 的上界内。