408数据结构算法-2012

#include <iostream>
#include <vector>

using namespace std;
struct LinkNode {
    char data;
    LinkNode *next;
};

void createLinkNode(LinkNode *link, vector<char> v) {
    LinkNode *head = link;
    for (char i: v) {
        LinkNode *temp = new LinkNode();
        temp->next = nullptr;
        temp->data = i;
        head->next = temp;
        head = head->next;
    }
}

void showLinkNode(LinkNode *link) {
//    link = link->next;
    while (link != nullptr) {
        cout << link << " ";
        link = link->next;
    }
    cout << endl;
}

LinkNode *findSuffix(LinkNode *A, LinkNode *B) {
    int lenA = 0, lenB = 0;
    LinkNode *pA = A->next, *pB = B->next;
    while (pA != nullptr) {
        lenA++;
        pA = pA->next;
    }
    while (pB != nullptr) {
        lenB++;
        pB = pB->next;
    }
    pA = A->next, pB = B->next;
    if (lenA > lenB) {
        for (int i = 0; i < lenA - lenB; i++) {
            pA = pA->next;
        }
    } else {
        for (int i = 0; i < lenB - lenA; i++) {
            pB = pB->next;
        }
    }
    while (pA != nullptr || pB != nullptr) {
        if (pA->data == pB->data) {
            return pA;
        }
        pA = pA->next, pB = pB->next;
    }
    return new LinkNode();
}

int main() {
    vector<char> c1 = {'l', 'o', 'a', 'd', 'i', 'n', 'g'};
    vector<char> c2 = {'b', 'e', 'i', 'n', 'g'};

    LinkNode *headA = new LinkNode();
    LinkNode *headB = new LinkNode();
    createLinkNode(headA, c1);
    createLinkNode(headB, c2);

    showLinkNode(headA);
    showLinkNode(headB);

    cout << findSuffix(headA, headB);
}