本文主要是介绍题记(26)--Sharing(链表公共后缀)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
一、题目内容
二、输入描述
三、输出描述
四、输入输出示例
五、完整C语言代码
一、题目内容
To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, "loading" and "being" are stored as showed in Figure 1.
二、输入描述
For each case, the first line contains two addresses of nodes and a positive N (<= 10^5), where the two addresses are the addresses of the first nodes of the two words, and N is the total number of nodes. The address of a node is a 5-digit positive integer, and NULL is represented by -1. Then N lines follow, each describes a node in the format: Address Data Next where Address is the position of the node, Data is the letter contained by this node which is an English letter chosen from {a-z, A-Z}, and Next is the position of the next node.
三、输出描述
For each case, simply output the 5-digit starting position of the common suffix. If the two words have no common suffix, output "-1" instead.
四、输入输出示例
输入：
11111 22222 9 67890 i 00002 00010 a 12345 00003 g -1 12345 D 67890 00002 n 00003 22222 B 23456 11111 L 00001 23456 e 67890 00001 o 00010 00001 00002 4 00001 a 10001 10001 s -1 00002 a 10002 10002 t -1输出：
67890 -1
五、完整C语言代码
AC代码~#include<stdio.h>
#include<stdlib.h>typedef struct Linklist {char ch;struct Linklist* next;int add;int nextadd;
} L;int Linklen(L* h) { // 求链表长度L* tmp = h->next;int len = 0;while (tmp != NULL) {len++;tmp = tmp->next;}return len;
}int main() {int n, f1, f2;while (scanf("%d%d%d", &f1, &f2, &n) != EOF) {L* a = (L*)malloc(n * sizeof(L)); // 结构体数组L* h1 = (L*)malloc(sizeof(L)); // 头节点L* h2 = (L*)malloc(sizeof(L));for (int i = 0; i < n; i++)scanf("%d %c %d", &a[i].add, &a[i].ch, &a[i].nextadd);int head1, head2;for (int i = 0; i < n; i++) { // 找出第一个节点的编号if (a[i].add == f1)head1 = i;if (a[i].add == f2)head2 = i;}h1->next = NULL;h2->next = NULL;h1->next = &a[head1];h2->next = &a[head2];L* tail1 = h1->next; // 尾指针L* tail2 = h2->next;while (tail1->nextadd != -1) { // h1链连接好int i = 0;for (i = 0; i < n; i++) {if (a[i].add == tail1->nextadd) {tail1->next = &a[i];tail1 = &a[i];break;}}}tail1->next = NULL;while (tail2->nextadd != -1) { // h2链连接好int i = 0;for (i = 0; i < n; i++) {if (a[i].add == tail2->nextadd) {tail2->next = &a[i];tail2 = &a[i];break;}}}tail2->next = NULL;int len1 = Linklen(h1);int len2 = Linklen(h2);int dist;L* longL; // long指向较长的链表L* shortL; // short指向较短的链表if (len1 >= len2) { // dist为二者长度差值longL = h1->next;shortL = h2->next;dist = len1 - len2;} else {longL = h2->next;shortL = h1->next;dist = len2 - len1;}while (dist > 0) { // 较长的先走dist步 目的是使二者对齐dist--;longL = longL->next;}longL = longL->next; // 二者都走一步（第一个节点就相等不算“公共后缀”）shortL = shortL->next;while (longL != NULL) { // 相等的节点则是公共后缀的第一个if (longL->ch == shortL->ch && longL->nextadd == shortL->nextadd) {printf("%d\n", longL->add);break;}longL = longL->next;shortL = shortL->next;}if (longL == NULL)printf("-1\n");}return 0;
}这篇关于题记(26)--Sharing(链表公共后缀)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
