`
// 要找到两个带头节点单链表的共同后缀起始位置，时间高效的核心思路是先计算两个链表的长度，让较长链表的指针先移动长度差的步数，再让两个指针同步遍历，首次相遇的节点就是共同后缀的起始位置。具体步骤如下：
// 遍历str1和str2，分别计算两个链表的长度len1和len2。
// 计算长度差diff = |len1 - len2|，让较长链表的头指针先向后移动diff步。
// 两个链表的指针同步向后遍历，直到指针指向的节点相同，该节点即为共同后缀的起始位置（若遍历至链表尾仍未相遇，则无共同后缀）。
// 该思路避免了暴力匹配的高时间复杂度，通过长度差对齐指针，实现一次遍历找到目标。
include <stdio.h>
include <stdlib.h>
include <math.h>
// 定义链表节点结构
typedef struct ListNode {
char data; // 存储字符数据
struct ListNode* next; // 指向下一节点的指针
} ListNode;
// 辅助函数：创建新节点
ListNode* createNode(char data) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 辅助函数：计算链表长度（不含头节点）
int getListLength(ListNode* head) {
int len = 0;
ListNode* cur = head->next; // 跳过头节点
while (cur != NULL) {
len++;
cur = cur->next;
}
return len;
}
// 核心函数：查找两个带头节点链表的共同后缀起始节点
ListNode* findCommonSuffix(ListNode* str1, ListNode* str2) {
if (str1 == NULL || str2 == NULL) {
return NULL; // 空链表无共同后缀
}
// 步骤1：计算两链表长度
int len1 = getListLength(str1);
int len2 = getListLength(str2);
int diff = abs(len1 - len2);// 步骤2：较长链表的指针先移动长度差
ListNode* p1 = str1->next; // str1数据节点起始指针
ListNode* p2 = str2->next; // str2数据节点起始指针
for (int i = 0; i < diff; i++) {if (len1 > len2) {p1 = p1->next;} else {p2 = p2->next;}
}// 步骤3：同步遍历，找首次相遇节点（地址相同）
while (p1 != NULL && p2 != NULL) {if (p1 == p2) {return p1; // 找到共同后缀起始节点}p1 = p1->next;p2 = p2->next;
}return NULL; // 无共同后缀
}
// 测试用例：模拟loading和being的链表结构
int main() {
// 1. 构建共同后缀部分：i -> n -> g
ListNode* node_i = createNode('i');
ListNode* node_n = createNode('n');
ListNode* node_g = createNode('g');
node_i->next = node_n;
node_n->next = node_g;
// 2. 构建str1（loading）：头节点 -> l -> o -> a -> d -> i -> n -> g
ListNode* head1 = createNode('*'); // 头节点（数据无意义）
ListNode* node_l = createNode('l');
ListNode* node_o = createNode('o');
ListNode* node_a = createNode('a');
ListNode* node_d = createNode('d');
head1->next = node_l;
node_l->next = node_o;
node_o->next = node_a;
node_a->next = node_d;
node_d->next = node_i;// 3. 构建str2（being）：头节点 -> b -> e -> i -> n -> g
ListNode* head2 = createNode('*'); // 头节点（数据无意义）
ListNode* node_b = createNode('b');
ListNode* node_e = createNode('e');
head2->next = node_b;
node_b->next = node_e;
node_e->next = node_i;// 4. 查找共同后缀
ListNode* commonNode = findCommonSuffix(head1, head2);
if (commonNode != NULL) {printf("共同后缀起始节点数据：%c\n", commonNode->data); // 输出'i'
} else {printf("两个链表无共同后缀\n");
}// （可选）释放链表内存（避免内存泄漏）
// 此处省略释放逻辑，实际使用时需遍历链表free所有节点return 0;
}
// 三、时间复杂度分析计算链表长度：1·遍历str1的时间为O(n)，遍历str2的时间为O(m)（n、m分别为两个链表的长度）。
// 2·指针移动与同步遍历：最长遍历次数为max(n,m)，时间为O(max(n,m))。整体时间复杂度为O(n + m)，这是单链表此类问题的最优时间复杂度（必须遍历完两个链表才能确定长度和共同节点）。
// 3·空间复杂度为O(1)，仅使用了常数个临时变量，未额外开辟与链表长度相关的空间。`