两个链表字符都相同，却没有公共后缀？2012年408的地址与尾部对齐

两个单词用带头结点的单链表保存。如果它们有共同后缀可以让后缀共用同一批结点不再各存一份。这道题要找到这批公共结点的第一个。比如loading和being都以ing结尾。下面只画数据结点前面各自还有一个头结点先确定我们到底在比较什么我先想到了两种比较字符相同或者结点地址相同。看图里的i两条链不是各有一个i而是两个前缀都接到了同一个i结点上。我们要找的是这个共同存储位置所以比较地址才对。如果我另建两条链各自也放i、n、g字符看起来完全一样但结点是两批题目要求的公共结点就不存在。反过来一旦p和q指向同一个结点后面还需要继续检查字符吗不用。这个结点只有一个next字段两边读到的next必然也是同一个。后面的n、g自然一起共享。所以我们要判断的是pq不是p-dataq-data。先用双重循环能找到吗可以。我让p从第一条链的前面往后走每到一个结点都让q从第二条链的开头再找一遍看有没有地址相同的结点。用图上的例子p在l、o、a、d时第二条链里都找不到同一个结点p走到i再扫第二条链就能在它的i处匹配到。外层从前往后所以第一次找到的正是共同后缀的起点。这个办法正确也不需要额外数组。但第一条链每前进一步第二条链又从头扫一次。两边长度为m和n时最坏要O(mn)。我们想省掉的就是这部分重复找。我想到从尾部一起看共同的部分既然在尾巴从后往前同时比较不就方便了第一条从尾部看g、n、i、d、a、o、l 第二条从尾部看g、n、i、e、bg、n、i是共同结点到d和e才分开。最后一个共同结点就是我们要的i。但单链表没有前驱指针。我接着想到逆置把两条链反过来就能往前走了。这里要特别看清两个尾巴并不独立。把loading逆置时原来的i-nextn会被改成指向d。being也连着这个i它接下来读到的就不再是n而是d。也就是说改第一条链的共享部分同时改到了第二条链。不能把它们当两条独立链各自原地反转再比较。用栈保存地址、从栈顶逆向比较可以保留原链但又多用了O(mn)空间。我们还能不能保留“尾部对齐”的想法只换一种走法不倒着走先把长出来的前缀走掉先看图上两条链的长度loading有7个数据结点being有5个差2。如果直接让p从l、q从b一起走会怎么样四步以后p才到iq已经到了g。它们经过的是同一段尾巴却没有在同一轮站到同一个结点上。只说“同时往前走”还不够。共同的i、n、g占3个位置。第一条在共同部分前面有l、o、a、d四个结点第二条有b、e两个前缀也差2。所以先让第一条的p走两步l到o再从o到a第二条的q仍在b。现在两边还剩多少个结点p这边a → d → i → n → g q这边b → e → i → n → g都是5个包括指针当前所指的结点。尾部还对齐着只不过我们不需要倒着走改成从这两个位置往前比较。这一轮pq剩余结点数长链先走两步后ab各5个两个各走一步de各4个再各走一步同一个i同一个i各3个第一轮地址不同第二轮也不同第三轮指到同一个i找到起点。三幅画的是同一组结点只移动p、q链上的next没有改。最后两个指针都落在一个i上不是各自落在一个字符相同的i上。此时停止不需要再走到n或g才确认。刚才我们是知道共同后缀有三个结点才把这幅图讲开。实际算法不知道这个长度但也不用知道两条链共同部分的长度一定相等所以总长度多出的那些位置只能来自不共同的前缀。先跳过总长度差两边剩下的非公共前缀就一样长了。再一起走才会在同一轮到达公共起点不需要试所有对齐位置。题目没给长度怎么办这也是我当时问到的地方。只给两个头指针我们不能直接假定m、n已经知道。先分别扫描两条链数出数据结点数量。再把p、q放回各自首数据结点让较长的一边先走长度差最后一起比较地址。如果两条链一样长就不用预走如果没有公共后缀一起走到NULL返回NULL。两条链都结束不表示NULL也是一个公共数据结点。#include stddef.h typedef struct Node { char data; struct Node *next; } Node; Node *firstSharedSuffix(Node *str1, Node *str2) { if (str1 NULL || str2 NULL) return NULL; size_t m 0, n 0; Node *p str1-next, *q str2-next; for (Node *t p; t ! NULL; t t-next) m; for (Node *t q; t ! NULL; t t-next) n; while (m n) { p p-next; --m; } while (n m) { q q-next; --n; } while (p ! NULL p ! q) { p p-next; q q-next; } return p; // 地址相同则是起点否则为 NULL }前面的两个for是在求长度。后面的两个while不是轮流处理整条链只有较长的那边会前进直到两个计数相等。比如7和5p前进两次m也减两次变成5和5。这里m、n此时表示的是剩余长度不再是最初的总长度。最后一段才是同步移动。因为两边剩余长度相同若没有相交p和q会一起变成NULL所以代码看p是否为空就够了。若相交p!q先变成假留下来的p就是起点。整个函数只读next没有逆置、释放或修改结点。输入须是无环、结点有效的链表有环时前面数长度就可能走不完。两条链分别扫描常数次总时间O(mn)额外空间O(1)。和倒数结点那题一样这里也从尾部想问题却只向前走不过这次先拉齐的是剩余长度不是让两根指针保持一个非零间距。题意按2012年408原卷第42题整理原卷来自厦门工学院公开备考资料。下面保留我的解题复盘C实现与验证是补充不是官方答案。附录完整验证程序参照用双重扫描比较地址速度慢但逻辑直观所有字符故意相同覆盖无共享、完全共享和不同前缀长度检查原next未改变。完整程序包含上面的题解函数和独立参照。保留源码是为了读者能自己改输入、定位错误不需要先读完它才能理解正文。gcc -stdc11 -Wall -Wextra -Werror -pedantic -fsanitizeaddress,undefined -fno-omit-frame-pointer lab.c -o lab ./lab#include assert.h #include limits.h #include stdbool.h #include stddef.h #include stdio.h #include stdlib.h typedef struct Node { char data; struct Node *next; } Node; Node *firstSharedSuffix(Node *str1, Node *str2) { if (str1 NULL || str2 NULL) return NULL; size_t m 0, n 0; Node *p str1-next, *q str2-next; for (Node *t p; t ! NULL; t t-next) m; for (Node *t q; t ! NULL; t t-next) n; while (m n) { p p-next; --m; } while (n m) { q q-next; --n; } while (p ! NULL p ! q) { p p-next; q q-next; } return p; // 地址相同则是起点否则为 NULL } int main(void) { size_t cases 0; for (int m 0; m 12; m) for (int n 0; n 12; n) for (int k 0; k 12; k) { Node left[12], right[12], shared[12]; for (int i 0; i k; i) { shared[i].data x; shared[i].next i 1 k ? shared[i 1] : NULL; } for (int i 0; i m; i) { left[i].data x; left[i].next i 1 m ? left[i 1] : k ? shared : NULL; } for (int i 0; i n; i) { right[i].data x; right[i].next i 1 n ? right[i 1] : k ? shared : NULL; } Node a {a, m ? left : k ? shared : NULL}, b {b, n ? right : k ? shared : NULL}; Node *oracle NULL; for (Node *p a.next; p !oracle; p p-next) for (Node *q b.next; q; q q-next) if (p q) { oracle p; break; } assert(firstSharedSuffix(a, b) oracle); for (int i 0; i m; i) assert(left[i].next (i 1 m ? left[i 1] : k ? shared : NULL)); for (int i 0; i n; i) assert(right[i].next (i 1 n ? right[i 1] : k ? shared : NULL)); cases; } assert(firstSharedSuffix(NULL, NULL) NULL); printf(PASS shared cases%zu\n, cases); return 0; }这次改写后重新以严格编译选项和AddressSanitizer、UndefinedBehaviorSanitizer运行了上面的完整C程序2197组前缀与公共后缀组合检查通过输出如下。题解代码与此前版本逐字相同。assert不能通过-DNDEBUG关闭。PASS shared cases2197有限测试是发现错误的证据不代替正文的正确性与复杂度理由。