每日编程Day 1，有哪些编程技巧和挑战值得探索？

本文共计703个文字，预计阅读时间需要3分钟。

问题描述：使用带头结点的单链表保存单词，当两个单词有相同的后缀时，可共享相同的后缀存储空间。例如，logging和being，如下图所示。设str1和str2分别指向两个单词所对应的单链表。

问题描述

假定采用带头结点的单链表保存单词，当两个单词有相同的后缀，则可共享相同的后缀存储空间，例如，“loaging”和“being”, 如下图所示。

设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为

请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置(如图中字符i所在结点的位置p)。

解决方法

（1）算法的基本思想

顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另外一个链表长k个结点，之后同步遍历两个链表。这样我们就能够保证它们同时到达最后一个结点。由于两个链表从第一个公共结点到链表的尾结点都是重合的。所以它们肯定同时到达第一个公共结点。于是得到算法思路：

①求它们的长度len1,len2；

②遍历两个链表，使p,q指向的链表等长；

③同步遍历两个链表，直至找到相同结点或链表结束。