本文主要是介绍【2012 统考真题/完整代码】找单词共同后缀的起始位置，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为data | next ,请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）。
思路
求出两个链表长度，让长的那个链表指针向前移动使两个链表末尾对齐（到最后一个节点的距离一样），然后同步向后移动，直到两个链表的指针地址一样时即为共同后缀起始位置。
下面为从构建链表到求出结果的完整代码。
完整代码
#include <iostream>
using namespace std;struct Node {char data;Node* next;Node(char val) : data(val), next(nullptr) {}
};class LinkedList {
private:Node* head;
public:LinkedList() {head = new Node(0); //头结点}void append(char val) {Node* current = head;while (current->next != nullptr) {current = current->next;}current->next = new Node(val);}void append(string val) {Node* current = head;while (current->next != nullptr) {current = current->next;}for (char ch:val){current->next = new Node(ch);current = current->next;}}void joint(LinkedList& list) { //连接两个链表Node* current = head;while (current->next != nullptr) {current = current->next;}current->next = list.getHead()->next;}Node* getHead() {return head;}void display() {Node* current = head;current = current->next; // 跳过头结点while (current != nullptr) {cout << current->data << " ";current = current->next;}}int length() {Node* current = head;int count = 0;while (current->next != nullptr) {count++;current = current->next;}return count;}void clear() {Node* current = head->next;while (current != nullptr) {Node* temp = current;current = current->next;delete temp;}head->next = nullptr;}//~LinkedList() {// clear(); // delete head;//}};int main() {LinkedList list1, list2,listend;list1.append("load");list2.append("be");listend.append("ing");list1.joint(listend);list2.joint(listend);list1.display();cout << endl;list2.display();cout << endl<<endl;int m, n;Node *p, *q;m = list1.length(); //分别计算两个链表的长度n = list2.length();//让两个链表从后往前长度相等for (p = list1.getHead(); m>n ; m--)p=p->next;for (q = list2.getHead(); n>m ; n--)q=q->next;//共同往后移动，直到找到相同的地址while (p->next != nullptr && q->next != p->next) {//只有共同后缀的地址才相同，前面遇到相同字母（如abcding，xcying的c）不会结束循环p=p->next;q=q->next;}cout << "起始位置为：" << p->next->data << endl;
}
这篇关于【2012 统考真题/完整代码】找单词共同后缀的起始位置的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
