《单链表、双链表、循环链表和静态链表的习题.doc》由会员分享，可在线阅读，更多相关《单链表、双链表、循环链表和静态链表的习题.doc（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、单链表、双链表、循环链表和静态链表的习题单链表、双链表、循环链表和静态链表的习题一、单项选择题1。关于线性表的顺序存储结构和链式存储结构的描述中,正确的是（ ）。线性表的顺序存储结构优于其链式存储结构。链式存储结构比顺序存储结构能更方便地表示各种逻辑结构。如频繁使用插入和删除结点操作，顺序存储结构更优于链式存储结构。顺序存储结构和链式存储结构都可以进行顺序存取A。 、 B。 、 C。 、 D。 、2。对于一个线性表既要求能够进行较快速地插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。A。顺序存储方式 B.链式存储方式 C。散列存储方式 D.以上均可以3。对于顺序存储的线性表
2、，其算法的时间复杂度为O（1)的运算应该是（）。A.将n个元素从小到大排序 B。删除第i个元素（1in）C.改变第i个元素的值（1=i=n） D.在第i个元素后插入一个新元素(1=inext;pnext=s； B.pnext=s-next； s-next=p;C。 qnext=s;snext=p； D。 pnext=s;s-next=q；7.给定有n个元素的一维数组，建立一个有序单链表的最低时间复杂度是（ ).A. O（1） B。 O（n） C. O（n2-) D. O（nlog2-n）8.将长度为n的单链表链接在长度为m的单链表后面，其算法的时间复杂度釆用大O形式表示应该是（ ）。A. O（
3、1） B。 O(n） C. O（m) D. O(n+m）9.单链表中，增加一个头结点的目的是为了（ ）。A。使单链表至少有一个结点 B。标识表结点中首结点的位置C.方便运算的实现 D。说明单链表是线性表的链式存储10。在一个长度为n的带头结点的单链表h上，设有尾指计r，则执行（ ）操作与链表的表长有关。A.删除单链表中的第一个元素B.删除单链表中最后一个元素C。在单链表第一个元素前插入一个新元素D.在单链表最后一个元素后插入一个新元素11.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ )； 对于不带头结点的单链表,则判定空表的条件为( )。A 。head=NULL B
4、.head-next=NULLC. head-next=head D。 head!=NULL12.下面关于线性表的一些说法中,正确的是( ）。A 。对一个设有头指针和尾指针的单链表执行删除最后一个元素的操作与链表长度无关B.线性表中每个元素都有一个直接前趋和一个直接后继C.为了方便插入和删除数据，可以使用双链表存放数据D。取线性表第i个元素的时间同i的大小有关13.某线性表中最常见的操作是在最后一个元素之后插入一个元素和删除第一个元素，则釆用（ ）存储方式最省时间。A。单链表 B.仅有头指针的单循环链表C。双链表 D。仅有尾指针的单循环链表14.在双链表中向p所指的结点之前插入一个结点q的操作
5、为( )。A。 p-prior=q;qnext=p；ppriornext=q;q-prior=p-prior;B 。qprior=pprior;ppriornext=q；q-next=p；ppriop=qnext；C. qnext=p;p-next=q；qpriornext=q;q-next=p；D 。p-prior-next=q； q-next=p; q-prior=pprior;pprior=q;15.在双向链表存储结构中，删除p所指的结点时必须修改指针( ）。A 。pllinkrlink=prlink； prlinkllink=p-llink；B.p-llink=pllink-llink
6、；pllinkrlink=p;C.p-rlink-llink=p； p-rlink = p-rlinkrlink;D .prlink=pllinkllink;pllink=p-rlinkrlink；16。在长度为n的有序单链表中插入一个新结点，并仍然保持有序的时间复杂度是（ ）。A. O（1) B. O(n） C。O(n2-) D。 O（nlog2-n)17。与单链表相比,双链表的优点之一是（ ）。A。插入、删除操作更方便 B。可以进行随机访问C.可以省略表头指针或表尾指针 D.访问前后相邻结点更灵活18.带头结点的双循环链表L为空的条件是( ）。A. Lprior=L&L-next=NULL
7、B。 L-prior=NULLL-next=NULLC. Lprior=NULL&L-next=LD. L-prior=L&Lnext=L19。 一个链表最常用的操作是在末尾插入结点和删除结点，则选用( ）最节省时间.A.带头结点的双循环链表 B。单循环链表C.带尾指针的单循环链表 D。单链表20。设对n（n1)个元素的线性表的运算只有4种：删除第一个元素；删除最后一个元素； 在第一个元素之前插入新元素；在最后一个元素之后插入新元素,则最好使用（ ）。A。只有尾结点指计没有头结点指针的循环单链表B。只有尾结点指针没有头结点指针的非循环双链表C.只有头结点指针没有尾结点指针的循环双链表D.既有头
8、结点指针也有尾结点指针的循环单链表21. 个链表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则选用（ ）最节省时间。A.不带头结点的单循环链表 B。双链表C。不带头结点且有尾指针的单循环链表 D.单链表22。静态链表中指针表示的是（ ）。A。下一元素的地址 B。内存储器地址C。下一个元素在数组中的位置 D.左链或右链指向的元素的地址23.需要分配较大的空间,插入和删除不需要移动元素的线性表，其存储结构为( ）。A.单链表 B。静态链表 C。顺序表 D。双链表二、综合应用题1。设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点。2。在带头结点的单链表L中，删除所有值为
9、x的结点，并释放其空间，假设值为x的结点不唯一,试编写算法以实现上述操作。3。设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。4。试编写在带头结点的单链表L中删除一个最小值结点的高效算法（假设最小值结点是唯一的）。5.试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间为O（1)。6.有一个带头结点的单链表L，设计一个算法使其元素递增有序.7.设在一个带表头结点的单链表中所有元素结点的数据值无序，试编写一个函数，删除表中所有大于最小值小于最大值的元素（若存在）.8.给定两个单链表，编写算法找出两个链表的公共结点。9。给定一个带表头结点的单链表，设head为头指针，结
10、点的结构为(data, next），data 为整型元素,next为指针,试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求:不允许使用数组作为辅助空间)。10.将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素,而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变。11.设C=a1， b1， a2， b2， ， an， bn为线性表,釆用带头结点的hc单链表存放,设计一个就地算法,将其拆分为两个线性表，使得A=a1, a2, an， B=bn, ， b2， b112.在一个递增有序的线性表中，有数值相同的元素存在
11、。若存储方式为单链表,设计算法去掉数值相同的元素，使表中不再有重复的元素。例如(7， 10， 10, 21， 30, 42, 42， 42, 51， 70）将变作（7， 10， 21， 30, 42， 51， 70）。13.假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表,并要求利用原来两个单链表的结点存放归并后的单链表。14。设A和B是两个单链表（带头结点），其中元素递增有序。设计一个算法从A和B 中公共元素产生单链表C，要求不破坏A、B的结点。15。已知两个链表A和B分别表示两个集合,其元素递增排列。编制函数,求A与
12、B 的交集，并存放于A链表中。16。两个整数序列A=a1, a2， a3，, am和B=b1， b2， b3,，bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的连续子序列。17。设计一个算法用于判断带头结点的循环双链表是否对称。18.有两个循环单链表，链表头指针分别为h1和h2，编写一个函数将链表h2链接到链表h1之后，要求链接后的链表仍保持循环链表形式。19.设有一个带头结点的循环单链表，其结点值均为正整数.设计一个算法,反复找出单链表中结点值最小的结点并输出，然后将该结点从中删除，直到单链表空为止，再删除表头结点。20.设头指针为L的带有表头结点的非循环双向链表,其每个结点
13、中除有pred(前驱指针）、data（数据）和next(后继指针)域外，还有一个访问频度域freq。在链表被启用前,其值均初始化为零.每当在链表中进行一次Locate（L， x)运算时，令元素值为x的结点中freq 域的值增1，并使此链表中结点保持按访问频度非增（递减)的顺序排列，同时最近访问的结点排在频度相同的结点的前面，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L, x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型.21。【2009年计算机联考真题】已知一个带有表头结点的单链表，结点结构为假设该链表只给出了头指针list。在不改变链表的前提下，请
14、设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的 data域的值，并返回1；否则，只返回0。要求：1)描述算法的基本设计思想.2）描述算法的详细实现步骤。3)根据设计思想和实现步骤，釆用程序设计语言描述算法（使用C、C+或Java语言实现），关键之处请给出简要注释.22。【2012年计算机联考真题】假定釆用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being的存储映像如下图所示。设strl和str2分别指向两个单词所在单链表的头结点,链表结点结构为，请设计一个时间上尽可能高效
15、的算法，找出由str1和str2所指向两个链表共同后缀的起始位置 (如图中字符i所在结点的位置p）。要求：1)给出算法的基本设计思想。2)根据设计思想，釆用C或C+或Java语言描述算法，关键之处给出注释。3）说明你所设计算法的时间复杂度。答案与解析一、单项选择题1. B两种存储结构有不同的适用场合，不能简单地说谁好谁坏，错误。链式存储用指针表示逻辑结构，而指针的设置是任意的,故可以很方便地表示各种逻辑结构；顺序存储则只能用物理上的邻接关系来表示逻辑结构，正确。在顺序存储中，插入和删除结点需要大量的移动元素，效率较低，的描述刚好相反.顺序存储结构既可以随机存取也能顺序存取,而链式结构只能进行顺
16、序存取，正确。2. B要求较快速地插入和删除，排除A、D.散列存储通过散列函数映射到物理空间，不能反映数据之间的逻辑关系，排除C。链式存储中的静态链表满足这一要求.3。 C对n个元素进行排序的时间复杂度最快也要O（n）（初始有序)，通常是O(nlog2-n)或O(n2-).在顺序表中删除第i个元素,或在第i个元素之后插入一个新元素，如想保持其它元素原来的顺序,时间复杂度为O（n)，因此A、B、D均错误.在顺序存储的线性表中更改第i个元素的值，直接用下标访问并重新赋值即可，时间复杂度为O（1)。4. D顺序存储方式同样适合图和树的存储，如满二叉树的顺序存储,错误.若线性表釆用顺序存储方式,则取其
17、第i个元素的时间与i的大小无关，错误。是静态链表的特有性质。单链表只能顺序查找插入位置，时间复杂度为O（n),若为顺序表，可釆用折半查找,时间复杂度可降至O（log2-n)， 正确。队列需要在表头删除元素，表尾插入元素,故釆用带尾指针的循环单链表较为方便,插入和删除的时间复杂度都是O(1)，正确。5。 AA中对于单链表和顺序表上实现的时间复杂度都为O（n)，但后者要移动很多元素，所以在单链表上实现效率更高。B和D效率刚好相反,C无区别。6。 Cs插入后，q成为s的前驱，而p成为s的后继,选项C满足此条件。7. D若先建立链表，然后依次直接插入建立有序表，则每插入一个元素就需遍历链表寻找插入位置
18、，此即链表的插入排序，时间复杂度为O(n2-).若先将数组排好序，然后建立链表，建立链表的时间复杂度为O(n），而数组排序的最少时间复杂度为O(nlog2-n），故时间复杂度为O(nlog2-n)。本题问最少时间复杂度，故选D。8。 C先遍历长度为m的单链表，找到这个长度为m的单链表的尾结点，然后将其next域置为另一个单链表的首结点，其时间复杂度为O(m）。9。 C单链表设置头结点的目的是为了方便运算的实现，主要好处体现在：第一，有头结点后,插入和删除数据元素的算法统一了，不再需要判断是否在第一个元素之前插入或删除第一个元素；第二，不论链表是否为空，链表指针不变.10。 B删除单链表的最后一
19、个结点需要置其前驱结点的指针域为NULL，故需要的时间为O(n),与表长有关。其他操作均与表长无关,读者可以自行模拟.11。 B, A在带头结点的单链表中，头指针head指向头结点,头结点的next域指向第1个元素结点，head-next=NULL表示该单链表为空。在不带头结点的单链表中，head直接指向第1 个元素结点，head=NULL表示该单链表为空.12。 C双链表能很方便地访问前驱和后继，故删除和插入数据较为方便。A显然错误。B表中第一个元素和最后一个元素不满足题设要求.D未考虑顺序存储的情况.B、C、D在删除尾结点时，都需要先查找其前驱结点，时间复杂度为O（n）。13. D在最后一
20、个元素之后插入元素，需要先找到最后一个元素，故A、B和C的时间复杂度均为O(n)。B因为没有特殊的指针指示头结点或尾结点，故需从某一结点向固定的方向顺序依次搜索插入和删除的位置，时间复杂度也为O(n)。D的两种算法的时间复杂度都是O（1),如下图所示。14. D为了在p之前插入结点q，可以将p的前一个结点的next域指向q，将q的next域指向 p，将q的prior域指向p的前一个结点，将p的prior域指向q.仅D满足条件.15。 A与上一题的分析基本类似，只不过这里是删除一个结点，注意将p的前、后两结点链接起来。注,请读者仔细对比上述两题,弄清双链表的插入和删除的方法。16. B假设单链表
21、递增有序（递减的情况同理），在插入数据为x的结点之前，先要在单链表中找到第一个大于x的结点的直接前驱p，在p之后插入该结点。查找过程的时间复杂度为O(n)，插入过程的时间复杂度为O(1），因此时间复杂度为O（n）。17. D在双链表中可以快速访问任何一个结点的前后相邻结点，而在单链表中只能快速访问任何一个结点的后继结点。18。 D循环单链表L判空的条件是头结点（头指针）的prior和next域都指向它自身。19. A在链表的末尾插入和删除一个结点时，需要修改其相邻结点的指针域.而寻找尾结点以及尾结点的前驱结点，只有带头结点的双循环链表所需要的时间最少。20. C对于A，删除尾结点p时，需要找到
22、*p的前一个结点，时间复杂度为O（n)。对于B，删除首结点*p时，需要找到*p结点,这里没有直接给出头结点指针，而通过尾结点的prior 指针找到p结点的时间复杂度为O(n）。对于D,删除尾结点*p时,需要找到*p的前一个结点，时间复杂度为O（n）.对于C,执行这4种算法的时间复杂度均为O(1）。21. C对于A，在最后一个元素之后插入一个元素的情况与普通单链表相同，时间复杂度为 O(n）;而删除表中第一个元素时，为保持单循环链表的性质（尾结点的指计指向第一个结点)，需要首先遍历整个链表找到尾结点，然后再执行删除操作，时间复杂度也为O（n)。对于B,双链表的情况与单链表的相同，一个是O（n），
23、一个是O(1）。对于C，与A的分析对比，因为已经知道了尾结点的位置，省去了遍历链表的过程，因此插入和删除的时间复杂度均为 O(1）。对于D，要在最后一个元素之后插入一个元素，需要遍历整个链表才能找到插入位置，时间复杂度为O（n）;删除第一个元素的时间复杂度为O（1).22. C静态链表中的指针又称游标，指示下一个元素在数组中的下标。23. B静态链表用数组表示，因此需要预先分配较大的连续空间，静态链表同时还具有一般链表的特点,即插入和删除不需要移动元素。二、综合应用题1。解答：设f（L，x)的功能是删除以L为首结点指针的单链表中所有值等于x的结点,则显然有 f（Lnext， x)的功能是删除以
24、Lnext为首结点指针的单链表中所有值等于x的结点。由此，可以推出递归模型如下：终止条件：f(L， x） 不做任何事情； 若L为空表或只有一个结点f(L, x)删除*L 结点；f(L-next, x); 若 L-data=x递归主体:f(L,x）f(Lnext， x）； 其他情况本题代码如下：1. void Del_X_3 （Linklist &L, ElemType x) 2. /递归实现在单链表L中删除值为x的结点3. LNode p; /p指向待删除结点4. if (L=NULL） /递归出口5. return；6.7. if (Ldata=x） /若L所指结点的值为x8. p=L; /
25、删除*L,并让L指向下一结点9. L=Lnext；10. free(p)；11. Del_X_3(L，x） ； /递归调用12. else /若L所指结点的值不为x13. Del_X_3 （L-next， x） ； /递归调用14. 算法需要借助一个递归工作栈,深度为O（n），时间复杂度为O（n）。有读者认为直接free掉p结点会造成断链，实际上因为L为引用，是直接对原链表进行操作，因此不会断链。2。解答：解法一：用p从头至尾扫描单链表，pre指向*p结点的前驱.若p所指结点的值为x，则删除，并让p移向下一个结点，否则让pre、p指针同步后移一个结点。本题代码如F :1. void Del_X
26、_1(Linklist &L， ElemType x)2. /L为带头的单链表，本算法删除L中所有值为x的结点3. LNode p=Lnext， *pre=L, q； /置 p 和 pre 的初始值4.5. while(p！=NULL)6. if(p-data=x）7. q=p； /q指向该结点8. p=pnext;9. pre-next=p； /删除q 结点10. free(q)； /释放 *q结点的空间11. else /否则,pre和p同步后移12. pre=p;13. p=p-next；14. /else15. /while16. 本算法是在无序单链表中删除满足某种条件的所有结点，这里
27、的条件是结点的值为x。实际上，这个条件是可以任意指定的，只要修改if条件即可，比如，我们要求删除值介于 mink和maxk之间的所有结点，则只需将if语句修改为if(pdatamink &p-datamaxk）.解法二：釆用尾插法建立单链表.用p指针扫描L的所有结点，当其值不为x时将其链接到L之后，否则将其释放。本题代码如下:1. void Del_X_2（Linklist L， ElemType x）2. /L为带头的单链表，本算法删除L中所有值为x的结点3. LNode p=3-next, *r=L, *q； /r指向尾结点,其切值为头结点4.5. while(p!=NULL）6. if
28、(pdata！=x） /*p结点值不为x时将其链接到L尾部7. rnext=p;8. r=p;9. p=p-next; /继续扫描10. else /p结点值为x时将其释放11. q=p；12. p=pnext; /继续扫描13. free(q）; /释放空间14. 15. /while16. r-next=NULL； /插入结束后置尾结点指针为NULL17. 上述两个算法扫描一遍链表，时间复杂度为O（n）,空间复杂度为O(1)。3。解答：考虑到从头到尾输出比较简单，本题的思路很自然地联系到借助上题链表逆置的方法来实现，改变链表的方向，然后就可以从头到尾实现反向输出了。此外，本题还可以借助一个
29、栈来实现，每经过一个结点时，将该结点放入栈中。在遍历完整个链表后，再从栈顶开始输出结点值即可。既然能用栈的思想解决，也就很自然地联想到了用递归来实现，每当访问一个结点时，先递归输出它后面的结点,再输出该结点自身，这样链表就反向输出了。如下图所示：本题代码如下：1. void R_Print（LinkList L)2. /从尾至头输出单链表L中每个结点的值3. if(Lnext！=NULL）4. R_Print (Lnext) ； /递归5. /if6. print (L-data) ； /输出函数7. 4。解答：算法思想:用p从头至尾扫描单链表，pre指向*p结点的前驱，用minp保存值最小的
30、结点指针（初值为p），minpre指向minp结点的前驱（初值为pre）。一边扫描，一边比较，若pdafa小于minpdara，则将p、pre分别赋值给minp、minpre，如下图所示。当p扫描完毕，minp指向最小值结点，minpre指向最小值结点的前驱结点，再将minp所指结点删除即可。本题代码如下：1. LinkList Delete_Min（LinkList &L）2. /L是带头结点的单链表,本算法删除其最小值结点3. LNode pre = L, p=prenext； /p 为工作指针，pre 指向其前驱4. LNode minpre=pre, *minp=p； /保存最小值结点
31、及其前驱5. while(p！=NULL)6. if（p-dataminp-data)7. minp=p; /找到比之前找到的最小值结点更小的结点8. minpre=pre;9. 10. pre=p; /继续扫描下一个结点11. p=pnext;12. 13. minprenext=minpnext; /删除最小值结点14. free(minp）;15. return L;16. 算法需要从头至尾扫描链表，时间复杂度为O(n），空间复杂度为O(1)。若本题改为不带头结点的单链表,则实现上会有所不同,留给读者自行思考。5。解答：解法一：将头结点摘下，然后从第一结点开始,依次前插入到头结点的后面（
32、头插法建立单链表），直到最后一个结点为止,则实现了链表的逆置,如下图所示。本题代码如下：1. LinkList Reverse_l（LinkList L)2. /L是带头结点的单链表,本算法将L就地逆置3. p=L-next； /p为工作指针，从第一个元素结点开始4. Lnext = NULL; /先将头结点L的next域置为NULL5. while (p!=NULL) /依次将元素结点摘下6. r=p-next; /暂存p的后继7. pnext=L-next; /将p结点插入到头结点之后8. L-next=p;9. p=r;10. 11. return L;12. 解法二：大部分辅导书都只介
33、绍解法一，这对读者的理解和思维是不利的。为了将调整指针这个复杂的过程分析清楚，我们借助图形来进行直观的分析.假设pre、p和r指向3个相邻的结点，如下图所示。假设经过若千操作，*pre之前的结点的指针都已调整完毕，它们的next都指向其原前驱结点。现在令p结点的next域指向pre 结点，注意到一旦调整指针的指向后，p的后继结点的链就断开了，为此需要用r来指向原 *p的后继结点.处理时需要注意两点：一是在处理第一个结点时，应将其next域置为NULL,而不是指向头结点（因为它将作为新表的尾结点）；二是在处理完最后一个结点后,需要将头结点的指针指向它。本题代妈如下:1. LinkList Rev
34、erse_2（LinkList L）2. /依次遍历线性表L,并将结点指针反转3. LNode *pre,*p=L-next,*r=pnext；4. pnext=NULL； /处理第一个结点5. while(r！=NULL) /r为空,则说明p为最后一个结点6. pre=p； /依次继续遍历7. p=r;8. r=r-next；9. p-next=pre; /指针反转10. 11. Lnext=p; /处理最后一个结点12. return L；13. 上述两个算法的时间复杂度为O(n)，空间复杂度为O（1）。6。解答:算法思想：釆用直接插入排序算法的思想，先构成只含一个数据结点的有序单链表，然
35、后依次扫描单链表中剩下的结点*p （直至p=NULL为止),在有序表中通过比较查找插入 p的前驱结点*pre，然后将p插入到*pre之后，如下图所示。本题代码如下:1. void Sort（LinkList &L)2. /本算法实现将单链表L的结点重排，使其递增有序3. LNode *p=Lnext, *pre;4. LNode *r=p-next； /r保持p后继结点指针,以保证不断链5. pnext=NULL; /构造只含一个数据结点的有序表6. p=r;7. while(p！=NULL）8. r=p-next; /保存p的后继结点指针9. pre=L;10. while (prenext
36、！=NULL prenextdatanext; /将*p 插入到*pre 之后13. pre-next=p；14. p=r； /扫描原单链表中剩下的结点15. 16. 7。解答：因为链表是无序的,所以只能逐个结点进行检查，执行删除.本题代码如下：1. void RangeDelete(LinkList &L, int min，int max)2. LNode *pr = L, *p=Llink; /p 是检测指针，pr 是其前驱3. while（p！=NULL)4. if (pdatamin&p-datalink=plink；6. free（p);7. p=prlink；8. else /否则
37、继续寻找被删结点9. pr=p；10. p=plink；11. 12. 8。解答：两个单链表有公共结点，也就是说两个链表从某一结点开始,它们的next都指向同一个结点。由于每个单链表结点只有一个next域,因此从第一个公共结点开始，之后它们所有的结点都是重合的，不可能再出现分叉。所以，两个有公共结点而部分重合的单链表，拓扑形状看起来像Y,而不可能像X.本题极容易联想到“蛮方法：在第一个链表上顺序遍历每个结点，每遍历一个结点，在第二个链表上顺序遍历所有结点,如果找到两个相同的结点，于是就找到了它们的公共结点。显然，该算法的时间复杂度为O（len1*len2）。接下来我们试着去寻找一个线性时间复杂
38、度的算法。先把问题简化：如何判断两个单向链表有没有公共结点？应注意到这样一个事实：如果两个链表有一个公共结点，那么该公共结点之后的所有结点都是重合的，即它们的最后一个结点必然是重合的。因此，我们判断两个链表是不是有重合的部分，只要分别遍历两个链表到最后一个结点.如果两个尾结点是一样的，说明它们有公共结点，否则两个链表没有公共的结点.然而，在上面的思路中，顺序遍历两个链表到尾结点的时候,并不能保证在两个链表上同时到达尾结点。这是因为两个链表长度不一定一样。但假设一个链表比另一个长k个结点，我们先在长的链表上遍历k个结点,之后再同步遍历，此时我们就能保证同时到达最后一个结点了.由于两个链表从第一个
39、公共结点开始到链表的尾结点，这一部分是重合的.因此,它们肯定也是同时到达第一公共结点的。于是在遍历中，第一个相同的结点就是第一个公共的结点。在这个思路中,我们先要分别遍历两个链表得到它们的长度,并求出两个长度之差。在长的链表上先遍历长度之差个结点之后,再同步遍历两个链表，直到找到相同的结点,或者一直到链表结束.此时，该方法的时间复杂度为O（len1+len2）。本题代码如下：1. LinkList Search_1st_Common（LinkList Ll, LinkList L2)2. /本算法实现在线性的时间内找到两个单链表的第一个公共结点3. int len1 = Length(L1）,
40、 len2 = Length (L2) ； /计算两个链表的表长4. LinkList longList， shortList； /分别指向表长较长和较短的链表5. if (len1len2） /L1 表长较长6. longList = Ll-next; shortList=L2-next；7. dist=len1len2； /表长之差8. else /L2表长较长9. longList=L2next; shortList=L1next；10. dist=len2 lenl; /表长之差11. 12. while（dist-) /表长的链表先遍历到第dist个结点，然后同步13. longList=longListnext;14. while （longList!=NULL） /同步寻找共同结点15.