题目

假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“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;
}