点击查看代码
// 要找到两个带头节点单链表的共同后缀起始位置，时间高效的核心思路是先计算两个链表的长度，让较长链表的指针先移动长度差的步数，再让两个指针同步遍历，首次相遇的节点就是共同后缀的起始位置。具体步骤如下：
// 遍历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 -> gListNode* 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 -> gListNode* 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 -> gListNode* 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)，仅使用了常数个临时变量，未额外开辟与链表长度相关的空间。