《数据结构复习题集(上).ppt》由会员分享，可在线阅读，更多相关《数据结构复习题集(上).ppt（43页珍藏版）》请在金锄头文库上搜索。
1、数据结构习题集宋婕第一二章重要概念：数据结构相关定义：数据结构=数据+结构 记作 Data_Structure=(D,S)其中, Data_Structure是数据结构的名称。D是数据元素的有限集合(一般为一个数据对象)S是D上关系的有限集.几个相关名词：存储结构 逻辑结构 现实中任何一个问题都可以定义为一个数据类型-称为抽象数据类型抽象数据类型Abstract Data Type ADT一个数学模型及定义在这个模型上的一组操作(或运算)的总称.抽象数据类型定义 抽象数据类型=数学模型+操作=数据结构+操作描述如下：ADT 抽象数据类型的名称 数据对象 数据关系 基本操作ADT抽象数据类型名时
2、间复杂度(空间复杂度雷同)通常选择对特定问题的最基本操作作为原操作，以原操作执行次数即语句频度作为算法的时间度量T(n)。算法分析一般步骤：1.计算出算法的各个语句的频度2.统计出算法的语句频度和T(n)3.给出T(n)的大O表示称为算法的时间复杂度T(n)=O(f(n)常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、k次方阶O(nk)、指数阶O(2n)。第一二章习题1数据结构在计算机中的表示称为数据的（存储结构）。2数据结构是相互之间存在一种或多种特定关系的数据元素的集合.3数
3、据结构在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（顺序存储结构）。4.定义一个整数序列的ADT需要记住此整数序列需要支持元素的位置概念。Integers数据对象：D=ci|ciDODO=INTi=1，2,nn=0数据关系：RNN=|ci-1,ciD0i=2，3,，n基本操作：voidclear();voidinsert(int);voidremove(int);voidsizeof();boolisEmpty();boolisInSet(int);5.写出下列代码段的平均时间复杂度。假定其中的所有变量都是整型。(a)a=b+c;d=a+e;(b)sum=0;for(i
4、=0;i3;i+)for(j=0;jn;j+)sum+;(c)sum=0;for(i=0;in*n;i+)sum+;(d)for(i=0;in-1;i+)for(j=i+1;jn;j+)tmp=Aij;Aij=Aji;Aji=tmp;(e)sum=0;for(i=1;i=n;i+)for(j=1;j=n;j*=2)sum+;(f)sum=0;for(i=1;i=n;i*=2)for(j=1;j=n;j+)sum+;T(n) =O( f(2) = O(1);常数阶时间复杂度 T(n) =O( f(n-1)*(n)/2) = O(n2); T(n) =O( f(3n) = O(n); 1阶时间复杂
5、度T(n) =O( f(n*log2n) = O(n*logn);T(n) =O( f(log2n*n) = O(logn*n);T(n) =O( f(n2) = O(n2); 2阶时间复杂度(g)AssumethatarrayAcontainsvalues,Randomtakesconstanttime,andsorttakessteps.for(i=0;in;i+)for(j=0;jn;j+)Aj=Random(n);sort(A,n);(h)AssumearrayAcontainsrandompermutationofthevaluesfrom0ton-1sum=0;for(i=0;in
6、;i+)for(j=0;Aj!=i;j+)sum+;(i)sum=0;if(EVEN(n)/EVEN(n)判断元素是否为偶数for(i=0;i1)if(ODD(n)n=3*n+1;elsen=n/2;T(n) =O( f(n*(n-1)/2) = O(n2);T(n) =O( f(n*n*log2n) = O(n2logn);T(n) =O( f(n+1)/2) = O(n);下限是(log n)，没有上限。(只有当n=2x时，此段代码执行次数最少，执行的次数为log2n)7.(代码题)输入三个数x,y,z 按照从小到大顺序输出将输入的三个数作为数组元素进行冒泡排序void main() in
7、t num=3; printf(Input three number:n); int anum,temp,i,j; for(i=0;inum;i+) scanf(%d,&ai); for(i=0;inum-1;i+) for(j=i+1;jaj) temp=ai; ai=aj;aj=temp; for(i=0;i=0)个数据元素的有限序列。一般表示为L=(a1,a2,ai,an)注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系，下面说的两种实现方式是指他们的存储结构。线性表的两种实现方式：顺序表 ：顺序存储的线性表又称为顺序表，是使用一组地址连续的存储单元，依次存储线性表中的数据元素，
8、从而使得逻辑上相邻的两个元素在物理地址上也相邻。链表：通过一组任意的存储单元来存储线性表中的数据元素，每一个链表结点，除了存放元素自身信息还需要存放指向其后继的指针。第三章习题1在下列序列中，不是线性表的是(a,true,c)。2线性链表中各链结点之间的地址（连续与否无所谓）。3如某链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点，（带头结点的双循环链表）存储方式最节省运行时间。4线性表的顺序存储结构特点是（ 可直接随机访问任一元素）。1.设A是一个线性表（al，a2，,an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？分析：假设pi是
9、在第i个元素之前插入元素的概率，则在长度为n的线性表中插入一个元素所需移动元素次数的平均次数为：2线性表可用顺序表或链表存储。试问：(1)两种存储表示各有哪些主要优缺点?(2)如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3)若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？Answer:(1)顺序表需要提前估计线性表的大小并且插入删除效率低需要移动大量结点，优点在于表中节点没有浪费存储空间，并且可以按位置随机访问；链表优点在于插入删除效率高，无需提前
10、估计表的大小，表中元素个数没有限制，缺点在于访问结点需要从表头遍历查找并且每个节点除了储存元素还需要附加空间存储指针。(2)链表表的大小不固定(3)顺序表，表大小固定，插入删除操作少，按位置随机存取速度快3针对带表头结点的单链表，试编写下列函数。(1)定位函数Locate：在单链表中寻找第i个结点。若找到，则函数返回第i个结点的地址；若找不到，则函数返回NULL。(2)求最大值函数max：通过一趟遍历在单链表中确定值最大的结点。(1)Node*LinkLocate(inti)if(inext;intj=0;while(p&j!=i)p=p-next;j+;if(p=null)return-1;
11、elsereturnp;(2)templateELinkMax()Node*p;p=head-next;Ej=p-data;while(p-next&p-datanext-data)p=p-next;j=p-next-data;returnj;(3)统计函数number：统计单链表中具有给定值x的所有元素。(4)建立函数create：根据一维数组an建立一个单链表，使单链表中各元素的次序与an中各元素的次序相同，要求该程序的时间复杂性为O(n)。(3)templateintLinkCount(Ea)Node*p;p=head-next;intcount=0;while(p)if(p-data=
12、a)count+;p=p-next;returncount;(4)templatevoidLinkCreate(Ea,intn)Node*p;p=head-next;/尾指针尾插法 for(inti=0;inext=temp;temp-data=ai;p=temp-next;5)整理函数tidyup：在非递减有序的单链表中删除值相同的多余结点。templatevoidLinkSort()Node*p=head-next,*temp;while(p!=null&p-next!=null)if(p-data=p-next-data)temp=p-next;p-next=temp-next;dele
13、tetemp;elsep=p-link;第四章1栈应用的典型事例是（）。A）排队 B）查找C）归并D）用“算符优先法”进行表达式求值2若用单链表来表示队列，则应该选用（）。A）带尾指针的非循环链表B）带尾指针的循环链表C）带头指针的非循环链表D）带头指针的循环链表3在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，这样主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个（）结构。A）堆栈B）队列C）数组D）线性表4设一个栈的入栈序列是ABCD，则借助于一个栈所得到的出栈序列不可能是（）。A）ABCDB）DCBAC）ACDBD）DABC
14、5一般情况下，将递归算法转换成等价的非递归算法应该设置（）。A）栈B）队列C）堆栈或队列D）数组6设栈的输入序列是1，2，n，若输出序列的第一个元素是n，则第i个输出元素是（）。A）n-i+1B）iC）n-iD）前面都不正确DBDBAA1有5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C第一个出栈，D第二个出栈的次序有哪几个？分析：栈特点：先进后出；元素C元素D为前两个出栈元素，说明AB已入栈，并且CD入栈后又出栈。可能的情况有三种。E元素未入栈时，BA依次出栈即为CDBAE；B元素出栈后E元素入栈然后EA再入栈即为CDBEA；E元素入栈后，EBA依次出栈即为CDE
15、BA2已知一个栈S的输入序列为abcd，下面两个序列能否通过栈的Push和Pop操作输出；如果能，请写出操作序列；如果不能，说明原因。(1)dbca(2)cbda分析：栈特点：先进后出；(1)dbca不可能若d第一个出栈，则只有dcba这种可能(2可能操作序列为：Push(a)Push(b)Push(c)Pop(c)Pop(b)Push(d)Pop(d)Pop(a)3.给一个链表增加一个成员函数，此函数用来将链表中的元素逆置。算法时间复杂度尽可能的小。Node*Reverse(Node*head)Node*p,*q;if(head=NULL)returnNULL;p=NULL;/*逆序后头指针
16、的next为NULL*/while(head-next)q=head-next;/*保存指针的下一个*/head-next=p;/*next指针反转*/p=head;/*指针后移*/head=q;/*指针后移*/head-next=p;/*处理逆序后的尾指针*/returnhead;4.存在一个非空的队列，以及一个空栈。写出一个算法去逆置队列中的元素，并且只能使用栈和队列的基本操作，在空间上只使能用一个变量空间。voidreverse(Queue&Q,Stack&S)Elementtemp;while(!Q.isEmpty()temp=Q.dequeue();S.push(temp);whil
17、e(!S.isEmpty()temp=S.pop();Q.enqueue(temp);5.花括号的匹配问题，题目要求，给出一个只有(和)的字符串，使用栈去判断字符串中的左右括号的使用是否正确，其中正确的含义包括：个数上是否正使用确以及配对上是否正确。a)如果字符串不正确则返回false，若字符串正确则返回true。提示：在任意时刻不可能存在右括号比左括号多的情况。(b)如果字符串不正确则返回出错元素在字符串中的下标，若字符串正确则返回true答案：a)利用栈进行匹配，从左往右遍历字符串，左括号入栈，右括号匹配栈顶元素，若匹配不到则字符串出错，若成功则左括号出栈；最后判断栈是否为空，不为空则出错
18、。boolbalance(Stringstr)StackS;intpos=0;while(str.charAt(pos)!=NULL)/遍历strif(str.charAt(pos+)=()/左括号入栈S.push();elseif(str.charAt(pos+)=)/右括号if(S.isEmpty()returnFALSE;/没有相匹配的左括号，出错elseS.pop();/匹配成功继续循环if(S.isEmpty()returnTRUE;/栈不为空说明左括号过多，出错elsereturnFALSE;b)从左往右遍历字符串，将左括号对应下标入栈，右括号匹配最新的左括号即为栈顶元素，若匹配不
19、到则字符串出错，直接返回当前右括号的下标；若成功则栈顶出栈；最后判断栈是否为空，不为空则出错。 int balance(String str) Stack S; int pos = 0; while (str.charAt(pos) != NULL)/将下标直接存入栈中 出错可以直接返回 if (str.charAt(pos+) = () S.push(pos); else if (str.charAt(pos+) = ) if (S.isEmpty() return pos; else S.pop(); if (S.isEmpty() return -1; else return S.pop
20、(); 第五章二叉树1.设某二叉树前序为abdcef，中序为dbaecf，画出此二叉树（南方名校经典试题）2有二叉树中序序列为：ABCEFGHD；后序序列为：ABFHGEDC；请画出此二叉树。3若一颗二叉树的前序遍历序列与后序遍历序列分别为1.2.3,4和4,3,2,1，则该二叉树的中序遍历不会是（C）。A)1234B)2341C)3241D)43214.在下列序列中，不能唯一地确定一颗二叉树的是（D）A)层次序列和中序序列B)先序序列和中序序列C)后序序列和中序序列D)先序序列和后序序列分析1：前序序列为LRN后序序列为NLR，由于前序序列与后序序列正好相反，因此不可能存在一个结点同时存在左
21、右孩子，即二叉树的高度为4，且1为根节点，因此在中序序列中1或者在序列首部或者在尾部，现考虑除去根节点的以2为根节点的子树。分析2：先序序列为NLR，后序序列为LRN虽然可以唯一确定一颗树中的根节点，但是无法划分左右子树，例如先序序列为AB，后序序列为BA5.已知二叉树的先序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果是什么，并且画出这颗二叉树。答：后序遍历结果为：CBEFDA6.已知二叉树的层次序列为ABCDEF，中序序列为BADCFE，则先序序列是什么，并且画出这颗二叉树。答：先序遍历结果为：ABCDEF7.表达式x*(y-z)+u的逆波兰式（后缀表达式）表示是（B
22、）。A）xyzuu-+B）xyz-*u+C）xyz*-u+D）+-*xyzu8.设有表达式：a*(b-c)/d+f/(g+h*i)，试给出此表达式的下面结果：二叉树表示；逆波兰式表示；中缀表示；逆波兰式表示(后缀即为左右根)：abc-*d/fghi*+/+中缀表示(即为左根右)：a*b-c/d+f/g+h*i9.已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8、11，试求对应哈夫曼树。步骤如下：(1)将w1、w2、，wn看成是有n棵树的森林(每棵树仅有一个结点)；(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树
23、根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林；(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。10.BuildtheHuffmancodingtreeanddeterminethecodesforthefollowingsetoflettersandweights:LetterABCDEFGHIJKLFrequency23571113171923313741Whatistheexpectedlengthinbitsofamessagecontainingcharactersforthisfrequencydistribution?209/83
24、126/l425571/HI24J34K/EF17G/D10/5C/ABl00h010i011e1000f1001j101d11000a1100100b1100101c110011g1101k111其中F代表总频度或权值,n代表总个数,li代表编码长度,fi代表频度本题中长度为3.2344511.将下列序列调整为大顶堆:10512321879410/512/3218/794答案：（10，5，12，3，2，1，8，7，9，4）从最后一非终端节点开始筛选10/512/3418/79210/512/9418/73210/512/9418/73210/912/7418/53212/910/7418/5
25、32大顶堆为12,9,10,7,4,1,8,5,3,212.使用数学归纳法证明：在一棵非空满K叉树中，n代表树中的分支节点，即非叶子节点，证明树中叶子节点的个数为(K-1)n+1；证明：当n=1时,即其中的叶子节点数为K,满足(K-1)*1+1=K,即成立；假设当n=x时，叶子节点数为(K-1)x+1成立；那么当n=x+1时，某一个叶子节点变成非叶子节点则会增加K-1个叶子节点。即最终叶子节点数目为：(K-1)x+1+K-1=(K-1)(x+1)+1成立。13.假设二叉树中每个结点所含数据元素均为单字母，以二叉链表为存储结构，试编写算法按如图所示的树状显示二叉树。分析：1）打印顺序ceabd，
26、对树来说是右根左的访问顺序；2）每个元素前的空白字符数等于它在树中的层数减一；voidInorder(BiTreebt,level)/level=1inti;if(bt!=NULL)/按右根左遍历二叉树Inorder(bt-rchild,level+1);/右for(i=0;idata);printf(n);Inorder(bt-lchild,level+1);/左14.写一个递归函数，名字叫做search，此函数带有两个参数，树的根节点，以及待查找的value值。如果value在树中存在则返回ture，反之返回false。答案：以根左右的方式遍历查找templateboolsearch(Bi
27、nNode*subroot,KeyK)if(subroot=NULL)returnfalse;if(subroot-value()=K)returntrue;if(search(bt-lchild,K)returntrue;if(search(bt-rchild,K)returntrue;15写一个递归算法，返回一颗二叉树的高度。答案：templateintheight(BinNode*subroot)if(subroot=NULL)return0;/空return1+max(height(subroot-lchild),height(subroot-rchild);16.写名为printRa
28、nge的递归函数。带有三个参数，分别是：一颗BST(二叉排序树)的根，以及一个lowvalue和一个highvalue。此函数的功能是将二叉排序树中值在lowvalue与highvalue之间的数据打印出来。要求尽可能少的访问二叉排序树中的结点。templatevoidprintRange(BinNode*root,intlow,inthigh)if(root=NULL)return;if(root-val()high)printRange(root-left(),low,high);elseif(root-val()right(),low,high);elseprintRange(root-
29、left(),low,high);PRINT(root-value();printRange(root-right(),low,high);排序1堆排序的时间复杂度是（D）。A）O(1) B）O(n) C）O(n2)D）O(nlogn)2.若一个具有N个顶点，K条边的无向图是一个森林（NK），则该森林中必有（C）棵树。A）KB）NC）N-KD）13每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（B）。A）冒泡排序B）简单选择排序C）希尔排序D）直接插入排序4快速排序执行一遍之后，已经到位的元素个数是（A）。A）1B）3C）n/4D）n/25数据表中有10000个元素，如果仅需求
30、出其中最大的10个元素，则采用（C）排序算法最节省时间。A）快速排序B）希尔排序C）堆排序D）直接选择排序6如果一棵树有n1个度为1的结点,有n2个度为2的结点,nm个度为m的结点,试问有多少个度为0的结点?试推导.7请画出右图所示的树所对应的二叉树。（8）8.判别序列（12，70，33，65，24，56，48，92，86，33）是否为堆，如果不是，则将它调整为大根堆。答案：因为堆为完全二叉树，因此只需要判断是不是所有节点，都大于或小于子节点，即节点n需要大于或小于2n节点和2n+1节点；序列不是堆如调整为大根堆为：(92，86，56，70，33，33，48，65，12，24)若调整为小根堆为
31、：(12，24，33，65，33，56，48，92，86，70)9给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18)。写出用下列算法从小到大排序时第一趟结束时的序列。（1）希尔排序（第一趟排序的增量为6）（2）快速排序（选第一个记录为枢轴）答案：(1)（4，2，16，6，8，28，12，10，20，30，18）(2)（6，2，10，4，8，12，28，30，20，16，18）10.编写一个处理整数关键码的插入排序。条件如下：输入的是一个栈（不是数组），并且程序中只允许使用一定的整数以及栈。结束时排序结果放在栈中，栈顶元素最小，在最差的情况下，算法的执行时间是(n2)
32、。voidStackSort(Stack&IN)StackTemp1,Temp2;while(!IN.isEmpty()/TransfertoanotherstackTemp1.push(IN.pop();IN.push(Temp1.pop();/Putbackoneelementwhile(!Temp1.isEmpty()/Processrestofelemswhile(IN.top()Temp1.top()/FindelemsplaceTemp2.push(IN.pop();IN.push(Temp1.pop();/Puttheelementinwhile(!Temp2.isEmpty()
33、/PuttherestbackIN.push(Temp2.pop();第十题实例如下：算法过程初始序列为：(18,12,56,9,55,8)插入排序基本思想是将第一个数据元素看成一个有序子序列，再依次从第二个记录起逐个插入到这个有序子序列中。 855 956121818第一个元素181256 955 8Temp1ININ181256 955 8Temp11218IN56 955 8Temp11812IN 955 8Temp1121856Temp2E=18E=12E=56ININ55 8Temp1 9121856IN 955 8Temp1121856Temp2Temp2IN 8Temp15556
34、1812 9Temp2IN Temp1 8 912185556E=19E=55E=8最终结果排序1在下述排序算法中，所需辅助存储量最多的是（D）。A）快速排序B）归并排序C）堆排序D）链式基数排序快速排序：O(logn)归并排序：O(n)堆排序：O(1)链式基数排序：O(n+r)r是基数2在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（A）。A）直接插入排序B）起泡排序C）简单选择排序D）基数排序3用一张表概括各种排序算法的时间代价、空间代价，特点。并总结各种情况下应选择的排序算法、并说明理由。排序算法排序算法平均时间代价平均时间代价辅助空间辅助空间特点特点直接插入排序直接插入
35、排序O(n2)O(1)稳定，数据基本有序时或者稳定，数据基本有序时或者n较小时较小时冒泡排序冒泡排序O(n2)O(1)稳定，效率较低稳定，效率较低简单选择排序简单选择排序O(n2)O(1)不稳定，数据较少，有序无序效率一样不稳定，数据较少，有序无序效率一样快速排序快速排序O(nlogn)O(logn)不稳定，数据乱序时不稳定，数据乱序时归并排序归并排序O(nlogn)O(n)稳定，空间足够且原始数据有序稳定，空间足够且原始数据有序堆排序堆排序O(nlogn)O(l)不稳定不稳定,只取前几个数据时只取前几个数据时Shell排序排序增量序列决定增量序列决定O(1)不稳定不稳定4.某个待排序的序列是
36、一个可变长度的字符串序列，这些字符串一个接一个地存储于唯一的字符数组中，另一个数组存储指向这个大字符串数组的索引（索引指向特定字符串的指针），请改写快速排序算法，对这个字符串序列进行排序。函数要修改索引数组，使得第一个指针指向最小字符串的起始位置。答案：在此题中，考虑到待排序的元素为字符串，并且另有一个数组index存储指向每一个字符串的指针。#defineNUM10char*testNUM=back,alert,cat,door,effective,grant,father,ideal,hand,zero;/存放所有字符的数据char*indexNUM;/假定只有NUM个待排字符串此处存放的
37、为指针for(i=0;iNUM;i+)indexi=&testi;/初始化index数组内的元素为指针指向每一个字符串在这个快速排序算法中，主要修改的地方有两个：一：每次比较的元素是两个字符串，因此应该用strcmp()比较函数；二：对于元素的交换，应该直接交换index指针即可，不需要交换test元素；voidswap(char*a,char*b)/交换指针char*temp;temp=a;a=b;b=temp;intPartition(intlow,inthigh)char*pivotkey;/定义一个指针intpivotindex=low;pivotkey=testlow;while(l
38、owhigh)while(low=0)high-;swap(indexlow,indexhigh);while(lowhigh&strcmp(testlow,pivotkey)next;q=L2-next;L-next=null;m=null;while(p&q)if(p-datadata)temp-data=p-data;/存入数据temp-next=m;/使用头插法建立链表L-next=temp;/头插法m=temp;/头插法p=p-next;elsetemp-data=q-data;/存入数据temp-next=m;L-next=temp;m=temp;q=q-next;/whilewh
39、ile(p)temp-data=p-data;/存入数据temp-next=m;L-next=temp;m=temp;p=p-next;while(q)temp-data=q-data;/存入数据temp-next=m;L-next=temp;m=temp;q=q-next;returnL;10.两个单链表L1和L2中的元素类型相同，要求从L1中删除那些同时在L2中出现的元素。若L1中有重复元素，要求只保留一个。分析所设计的算法的时间复杂度。Linkmerge(LinkL1,LinkL2)Linkp,q,temp,pre;p=L1-next;temp=p-next;pre=L1;/从L1的第二
40、个元素开始比较while(p)/对L1依次遍历，删除L1中重复的元素只保留一个while(temp)if(p-data!=temp-data)temp=temp-next;elsepre-next=pre-next-next;break;pre=p;p=p-next;/记录当前节点的前驱节点便于删除pre=L1;p=L1-next;temp=L2-next;/从L2的第一个元素开始比较while(p)/对L1中的元素，与L2中逐个比较，删除相同的元素while(temp)if(p-data!=temp-data)temp=temp-next;elsep-next=p-next-next;break;pre=p;p=p-next;/记录当前节点的前驱节点便于删除returnL1；;时间复杂度为O(n2)(假设链表L1与L2的规模均为n)Thanks
