数据结构常见编程题小结

1、单链表因为单链表要考虑的可能性比较少，所以单链表的题目比较简单，而且比较常考。特别要注意的是链表的数据的插入和删除，因为(没有头节点)的单链表在第一个元素之前插入和删除和最后一个元素的插入删除需要特别考虑。做题时，最好把单链表的示意图画出来，这样就很方便写代码了。常用技巧：快慢指针，拆分链表数据结构定义如下C++Code1structListNode{intval;//值ListNode*next;//下一个元素4}；ListNode(intx):val(x),next(NULL){}4}；下面是一些常考的题目：(1)LinkedListCycle禺断一个链表是否有环最好的方法是时间复杂度0(n)，空间复杂度0(1)的。设置两个指针，一个快一个慢，快的指针每次走两步，慢的指针每次走一步，如果快指针和慢指针相遇，则说明有环。(如何证明，上网找找)代码实现如下C++Code1234123456789101112131415161718//LeetCode,LinkedListCycle//时间复杂度0(n),空间复杂度O(1)classSolution{public:boolhasCycle(ListNode*head){//设置两个指针，一个快一个慢ListNode*slow=head,*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast)returntrue;}returnfalse;};(2)LinkedListCycleII琏表有环，找出环的起始点当fast与slow相遇时，slow肯定没有遍历完链表，而fast已经在环内循环了n圈(1n)。假设slow走了s步，则fast走了2s步(fast步数还等于s加上在环上多转的n圈)，设环长为r，则：2s=s+nrs=nr设整个链表长L,环入口点与相遇点距离为a,起点到环入口点的距离为x,则x+a=nr=(n-1)r+r=(n1)r+Lxx=(n1)r+(L-x-a)L-x-a为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于n1圈内环+相遇点到环入口点，于是我们可以从head开始另设一个指针slow2，两个慢指针每次前进一步,它俩一定会在环入口点相遇。C++Code1//LeetCode,LinkedListCycleII2//时间复杂度0(n),空间复杂度0(1)3classSolution4{5public:6ListNode*detectCycle(ListNode*head)7{8ListNode*slow=head,*fast=head;9while(fast&&fast->next)10{11slow=slow->next;12fast=fast->next->next;13if(slow==fast)14{15ListNode*slow2=head;16while(slow2!=slow)17{18slow2=slow2->next;19slow=slow->next;20}21returnslow2;22}23}24returnnullptr;25}26};3)AddTwoNumberYouaregiventwolinkedlistsrepresentingtwonon-negativenumbers.Thedigitsareorderandeachoftheirnodescontainasingledigit.Addthetwonumbersandreturnitasalinkedlist.Input:(2->4->3)+(5->6->4)Output:7->0->8代码实现如下：C++Code1//LeetCode,AddTwoNumbers2//跟AddBinary很类似3//时间复杂度0(m+n),空间复杂度0(1)4classSolution5{6public:7ListNode*addTwoNumbers(ListNode*l1,ListNode*l2)8{9ListNodedummy(-1);//头节点10intcarry=0;11ListNode*prev=&dummy;12for(ListNode*pa=l1,*pb=l2;13pa!=nullptr||pb!=nullptr;14pa=pa==nullptr?nullptr:pa->next,15pb=pb==nullptr?nullptr:pb->next,16prev=prev->next)17{18constintai=pa==nullptr?0:pa->val;19constintbi=pb==nullptr?0:pb->val;20constintvalue=(ai+bi+carry)%10;21carry=(ai+bi+carry)/10;22prev->next=newListNode(value);//尾插法23}24if(carry>0)25prev->next=newListNode(carry);26returndummy.next;27}28};4)PartitionList描述Givenalinkedlistandavaluex,partitionitsuchthat allnodeslessthanxcomebeforenodesgreaterthanorequaltox.Youshouldpreservetheoriginalrelativeorderofthenodesineachofthetwopartitions.Forexample,Given1->4->3->2->5->2andx=3,return1->2->2->4->3->5.C++Code1//LeetCode,PartitionList2//时间复杂度0(n),空间复杂度0(1)3classSolution4{5public:6ListNode*partition(ListNode*head,intx)7{8ListNodeleft_dummy(-1);//头结点9ListNoderight_dummy(-1);//头结点10autoleft_cur=&left_dummy;11autoright_cur=&right_dummy;12for(ListNode*cur=head;cur;cur=cur->next)13{14if(cur->val<x)15{16left_cur->next=cur;17left_cur=cur;18}-19else20{21right_cur->next=cur;22rightcur=cur;23}-24}25left_cur->next=right_dummy.next;26right_cur->next=nullptr;27returnleftdummy.next;28}-29};302、栈和队列基本概念：手动实现一个栈或者队列。剑指offer上面的最大栈的实现。3、字符串常用C语言库实现C++Code1char*strcpy(char*dst,constchar*src){2if(dst==src)returndst;3assert(dst!=NULL&&src!=NULL);4char*addr=dst;5while((*dst++=*src++)!='\0');

6returnaddr;7}8intstrcmp(constchar*s,constchar*t){9assert(s!=NULL&&t!=NULL)10while(*s&&*t&&*s==*t)11{12++s;13++1；14}15return(*s-*t);16}17voidmemcpy(void*dst,constvoid*src,intcount){18assert(dst!=NULL&&src!=NULL);19void*addr=dst;20while(cout--){21*(char*)dst=*(char*)src;22dst=(char*)dst++;23src=(char*)src++;24}25returnaddr;26}27intmemcmp(constvoid*s,constvoid*t,intcount){28assert(s!=NULL&&t!=NULL);29while(*(char*)s&&*(char*)t&&*(char*)s=*(char*)t30&&count--){31s=(char*)s++;32t=(char*)t++;33}34return(*(char*)s-*(char*)t);35}4、数组TwoSumGivenanarrayofintegers,findtwonumberssuchthattheyadduptoaspecifictargetnumber.ThefunctiontwoSumshouldreturnindicesofthetwonumberssuchthattheyadduptothetarget,whereindex1mustbelessthanindex2.Pleasenotethatyourreturnedanswers(bothindex1andindex2)arenotzero-based.Youmayassumethateachinputwouldhaveexactlyonesolution.Input:numbers={2,7,11,15},target=9Output:true

分析：先排序，然后左右夹逼，排序O(nlogn),左右夹逼0(n)，最终O(nlogn)voidqsor±(ini：B[]』intloWjinthigh)if(low>=high)return■intfirst=intfirst=loWjintlast二highjintkey=a[while(firsiz空扑厂用字表的第—个记录作为枢轴料while(first<last&&a[last]>=key)--last:a[first]=a[last]j 将比.第一个小的移到低端米/[first];尸将比第一个大的移到高端while(first<last&&a[first]<=key)++first■ [first];尸将比第一个大的移到高端a[last]=a[ _a_ _ _qsor七IoWja_ _ _qsor七IoWjfirs七-1)■qsort(ajfirst+1』high)jbooltowSum(int*arr,intlen,inttarget){intleft=0;intright=len-1;qsort(arr,0,len-1);while(left<right){if(arr[left]+arr[right]==target){returntrue;}elseif(arr[left]+arr[right]<target){left++;}else{right--;}}returnfalse;}2)SingleNumber描述

Givenanarrayofintegers,everyelementappearstwiceexceptforone.Findthatsingleone.Note:Youralgorithmshouldhavealinearruntimecomplexity.Couldyouimplementitwithoutusingextramemory?分析异或，不仅能处理两次的情况，只要出现偶数次，都可以清零。C++Code1//LeetCode,SingleNumber2//时间复杂度0(n),空间复杂度0(1)3classSolution4{5public:6intsingleNumber(intA[],intn)7{8intx=0;9for(size_ti=0;i<n;++i)10xA=A[i];11returnx;12}13};3)SearchinRotatedSortedArray题目意思：给定一个已排序数组，旋转了几次的，然后在这个旋转的数组里面查找一个目标值。分析二分查找，难度主要在于左右边界的确定。C++Code1//LeetCode,SearchinRotatedSortedArray2//时间复杂度0(logn),空间复杂度0(1)3classSolution4{5public:6intsearch(intA[],intn,inttarget)7{8intfirst=0,last=n;9while(first!=last)10{11constintmid=(first+last)/2;12if(A[mid]==target)13returnmid;14if(A[first]<=A[mid])15{16if(A[first]<=target&&target<A[mid])17last=mid;18else

19202first=mid+19202}else{if(A[mid]<target&&target<=A[last-1]first=mid+1;elselast=mid;}}return-1;}}；5、二叉树二叉树的基本概念：度：某节点所拥有的子树的个数称为该节点的度；树中各个节点读的最大值称为该树的度。节点的层数、树的深度：规定根节点的层数为1，对于其余任何节点，若某节点在第k层，则其孩子节点在第k+1层。树中所有节点的最大层数称为树的深度，也称为树的高度。满二叉树：在一颗二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。完全二叉树对一颗具有n个节点的二叉树按层序编号，如果编号为i(1<=i<=n)的节点与同样深度的满二叉树中编号为i的节点在二叉树中的位置完全相同，则这颗二叉树称为完全二叉树。(5)二叉查找树二叉查找树，或者是一颗空的二叉树，或者是具有如下性质的二叉树：若它的左子树不空，则左子树上所有节点的值均小于根结点的值。若它的右子树不空，则右子树上所有节点的值均大于根节点的值(3)它的左右子树也都是二叉查找树。二叉树解题思路：主要是通过递归解决问题。见到二叉树的题目，优先从递归方向考虑。递归都需要返回的，考虑好返回的边界条件是什么，一般是当节点是空的时候就返回。(1)二叉树的遍历(递归的比较简单，上网看看)非递归前序：使用栈实现C++Code1//LeetCode,BinaryTreePreorderTraversal

2//使用栈，时间复杂度0(n),空间复杂度0(n)3classSolution4{5public:6vector<int>preorderTraversal(TreeNode*root)7{8vector<int>result;9constTreeNode*p;10stack<constTreeNode*>s;11p=root;12if(p!=nullptr)s.push(p);13while(!s.empty())14{15p=s.top();16s.pop();17result・push_back(p->val);18if(p->right!=nullptr)s.push(p->right);19if(p->left!=nullptr)s.push(p->left);20}21returnresult;22}23};非递归中序遍历：使用栈实现C++Code1//LeetCode,BinaryTreeInorderTraversal2//使用栈，时间复杂度0(n),空间复杂度0(n)3classSolution4{5public:6vector<int>inorderTraversal(TreeNode*root)7{8vector<int>result;9constTreeNode*p=root;10stack<constTreeNode*>s;11while(!s.empty()||p!=nullptr)12{13if(p!=nullptr)14{15s.push(p);16p=p->left;17}18else19{

20P=s.top();21s.pop()；22result・push_back(p->val);23p=p->right;24}25}26returnresult;27}28｝；非递归后序遍历：C++Code1//LeetCode,BinaryTreePostorderTraversal2//使用栈，时间复杂度0(n),空间复杂度0(n)3classSolution4{5public:6vector<int>postorderTraversal(TreeNode*root)7{8vector<int>result;9/*p,正在访问的结点，q,刚刚访问过的结点*/10constTreeNode*p,*q;11stack<constTreeNode*>s;12p=root;13do14{15while(p!=nullptr) /*往左下走*/16{17s.push(p);18p=p->left;19}20q=nullptr;21while(!s.empty())22{23p=s・top();24s.pop();25/*右孩子不存在或已被访问，访问之*/26if(p->right==q)27{28result.push_back(p->val);29q=p;/*保存刚访问过的结点*/30}31else32{333435363733343536373839404142s.push(p);/*先处理右子树*/p=p->right;break;}}}while(!s.empty());returnresult;43 }44};层次遍历：描述Givenabinarytree,returnthelevelordertraversalofitsnodes'values.(ie,fromleftlevelbylevel).Forexample:Givenbinarytree{3,9,20,#,#,15,7},3/\920/\157returnitslevelordertraversalas:[,[9,20],[15,7]]层次遍历，是广度搜索，使用队列实现：C++Code121234567891011//递归版，时间复杂度0(n),空间复杂度0(n)classSolution{public:vector<vector<int>>levelOrder(TreeNode*root){vector<vector<int>>result;traverse(root,1,result);returnresult;

12voidtraverse(TreeNode*root,size_tlevel,vector<vect13or<int>>&result)14{15if(!root)return;if(level>result・size())result.push_back(vector<int>());result[level-1]・push_back(root->val);traverse(root->left,level+1,result);}};traverse(root->right,level+1,result);(2)SameTree判断两棵树是否一样，二叉树常用的思想是递归，用好递归C++Code1//递归版2//LeetCode,SameTree3//递归版，时间复杂度0(n),空间复杂度O(logn)4classSolution5{6public:7boolisSameTree(TreeNode*p,TreeNode*q)8{9if(!p&&!q)returntrue;//终止条件10if(!p||!q)returnfalse;//剪枝11returnp->val==q->val//二方合并12&&isSameTree(p->left,q->left)13&&isSameTree(p->right,q->right);14}15};3)SymmetricTree判断两棵树是否是镜像的，同样采用递归实现C++Code1//LeetCode,SymmetrieTree2//递归版，时间复杂度0(n),空间复杂度O(logn)3classSolution4{5public:6boolisSymmetric(TreeNode*root)7{8returnroot?isSymmetric(root->left,root->right)9:true;10}11boolisSymmetric(TreeNode*left,TreeNode*right)12{1311213112345678910111213141516balancedHeight(TreeNode*root)returnif(!left&&!right)returntrue;//终止条件if(!left||!right)returnfalse;//终止条件returnleft->val==right->val//三方合并&&isSymmetric(left->left,right->right)&&isSymmetric(left->right,right->left);}};4)BalancedBinaryTree判断一棵树是否是平衡的。C++Code//LeetCode,BalaneedBinaryTree//时间复杂度O(n),空间复杂度O(logn)classSolution{public:boolisBalaneed(TreeNode*root){returnbalancedHeight(root)>=0;}/**Returnstheheightof'root'if'root'isabalaneedtree,otherwise,returns'-1'・*/int{if(root==nullptr)return0;//终止条件intleft=balancedHeight(root->left);intright=balancedHeight(root->right);if(left<0||right<0||abs(left-right)>1)-1;//剪枝returnmax(left,right)+1;//三方合并}};4)二叉查找树判断是否是二叉查找树ValidateBinarySearchTreeC++Code1//LeetCode,ValidateBinarySearchTree2//时间复杂度0(n),空间复杂度0(\logn)3classSolution4{5public:6boolisValidBST(TreeNode*root)7{

8returnisValidBST(root,INT_MIN,INT_MAX);9}10boolisValidBST(TreeNode*root,intlower,intupper)11{12if(root==nullptr)returntrue;13returnroot->val>lower&&root->val<upper&&isValidBST(root->left,lower,root->val)■;}};&&isValidBST(root->right,root->val,upper)5)一颗树的最大深度C++Code1//LeetCode,MaximumDepthofBinaryTree2//时间复杂度0(n),空间复杂度0(logn)3classSolution4{5public:6intmaxDepth(TreeNode*root)7{8if(root==nullptr)return0;9returnmax(maxDepth(root->left),maxDepth(root->right))+110■;}};(6)一棵树的最小深度C++Code1//LeetCode,MinimumDepthofBinaryTree2//递归版，时间复杂度0(n),空间复杂度0(logn)3classSolution4{5public:int minDepth(const TreeNode *root)TOC\o"1-5"\h\z{returnminDepth(root,false);}10private:staticintminDepth(constTreeNode*root,boolhasbrother){if(!root)returnhasbrother?INT_MAX:0;return1+min(minDepth(root->left,root->right!=NULL),minDepth(root->right,root->left!=NULL));

(7)(7)PathSum描述Givenabinarytreeandasum,determineifthetreehasaroot-to-leafpathsuchthataddingupallthevaluesalongthepathequalsthegivensum.Forexample:Giventhebelowbinarytreeandsum=22,A//\11 13 4/\\7 2 1returntrue,asthereexistaroot-to-leafpath5->4->11->2whichsumis22.C++Code12345123456789101112//LeetCode,PathSum//时间复杂度O(n),空间复杂度O(logn)classSolution{public:boolhasPathSum(TreeNode*root,intsum){//if(root==nullptr)returnfalse;if(root->left==nullptr&&root->right==leafreturnsum==root->val;returnhasPathSum(root->left,sum-root->val)||hasPathSum(root->right,sum-root->val)}};8)两个结点的最低公共祖先二叉查找树版本C++Code1//copyright@eriol20112//modifiedbyJuly20143publicintquery(Nodet,Nodeu,Nodev)4{5intleft=u.value;intright=v.value;Nodeparent=null;

891011121314151617181920212223242526272829303132333435363738394041通〕++1234567//二叉查找树内，如果左结点大于右结点，不对，交换if(left>right){inttemp=left;left=right;right=temp;}while(true){//如果t小于u、v,往t的右子树中查找if(t・value<left){parent=t;t=t・right;//如果t大于u、v,往t的左子树中查找}elseif(t・value>right){parent=t;t=t.left;}elseif(t・value==left||t・value==right){returnparent.value;}else{returnt・value;}}}Code//copyright@allantop2014-1-22-20:01node*getLCA(node*root,node*node1,node*node2){if(root==null)returnnull;if(root==node1||root==node2)returnroot;

8989101112131415161718if(left!=null&&right!=null)returnroot;elseif(left!=null)returnleft;elseif(right!=null)returnright;elsereturnnull;}6、二分查找(看剑指offer吧)7、哈希表基本概念：散列函数的构造方法：除留余数法hash(key)=key%p(p<=m)1、散列表冲突处理的方法之链地址法的实现将所有哈希地址为i的元素构成一个成为同义词的链表中，并将链表的头指针存放在第i个单元中，增删查改都在这里进行。EkersEderlyAttleeAltonBurkeBroadBlumAttleeAltonBurkeBroadBlumHecht2、散列表冲突处理方法之开放地址法。（线性探测再散列）HO=hash（key）,如果有冲突放到下一个坐标处（下一个坐标为空）8、排序经典的排序算法：基本概念：排序的稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj,且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。表9T—1排序方床平均情琨■好情况■坏1W况摘助畫伺稳启性會泡排序o胁O(n)0(J?)0(1)简单选择排序0(於0(/7)0(加0(1)直接蜡人排序0(於0(/7)0(朋0(1)章冊序O(nlog?7)-OCrf1)0(^)0(小0(1)不穂定芈排序O(nlog/?)O(nlog/i)0⑴不稽定归幷排序O(rtlog/i)OCrtlog/i)O(flldgn)O(n)做速排序0{n!og/j)Ofnlogn)0(旳odogn)不毬定1）快速排序：主要掌握快速排序的一次排序是怎么排出来的。还要快速排序的改进方法是如

何实现的（改进关键在于枢纽元选择（随机法，），还有就是对于小数组插入排序比快速排序好）。下面是一个简单的实现：（未改进，双向比较）C++Code1voidQsort(inta[],intlow,inthigh)2{3if(low>=high)4{5return;6}7intfirst=low;8intlast=high;9intkey=a[first];/*用字表的第一个记录作为枢轴*/10while(first<last)11{12while(first<last&&a[last]>=key)13--last;14a[first]=a[last];/*将比第一个小的移到低端*/15while(first<last&&a[first]<=key)16++first;17a[last]=a[first];/*将比第一个大的移到高端*/18}19a[first]=key;/*枢轴记录到位*/20Qsort(a,low,first-1);21Qsort(a,first+1,high);22}（2）堆排序：主要理解如何建最大堆。理解堆究竟是什么来的C++Code123456712345678910111213*或者每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆*//*堆排序就是利用堆进行排序的方法•基本思想是:将待排序的序列构造成一个大顶堆.此时,整个序列的最大值就是堆顶*的根结点•将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新*构造成一个堆，这样就会得到n个元素的次大值•如此反复执行，便能得到一个有序序列了*/14/*时间复杂度为0（nlogn）,好于冒泡，简单选择，直接插入的0（n八2）*/1516//构造大顶堆#defineleftChild(i)(2*(i)+1)voidpercDown(int*arr,inti,intN){inttmp,child;for(tmp=arr[i];leftChild(i)<N;i=child){child=leftChild(i);if(child!=N-1&&arr[child+1]>arr[child])child++;if(arr[child]>tmp)arr[i]=arr[child];elsebreak;}arr[i]=tmp;}voidHeapSort(int*arr,intN){inti;for(i=N/2;i>=0;i--)percDown(arr,i,N);for(i=N-1;i>0;i--){swap1(&arr[0],&arr[i]);percDown(arr,0,i);}}（3）归并排序：主要理解递归分治的思想是如何解决问题的C++Code1/**********************************************************2**********************/3/*假设初始序列含有n个记录，则可以看成n个有序的子序列，每个子序列的4长度为1,然后5*两两归并，得到（不小于n/2的最小整数）个长度为2或1的有序子序列，6再两两归并，・・・7*如此重复,直至得到一个长度为n的有序序列为止，这种排序方法称为2路

89891011121314151617181920212223242526272829303132333435363*时间复杂度为0(nlogn),空间复杂度为0(n+logn),如果非递归实现归并，则避免了递归时深度为logn的栈空间*空间复杂度为0(n)*//*lposisthestartoflefthalf,rposisthestartofrighthalf*/voidmerge(inta[],inttmp_array[],intlpos,intrpos,intrightn){inti,leftn,num_elements,tmpos;leftn=rpos-1;tmpos=lpos;num_elements=rightn-lpos+1;/*mainloop*/while(lpos<=leftn&&rpos<=rightn)if(a[lpos]<=a[rpos])tmp_array[tmpos++]=a[lpos++];elsetmp_array[tmpos++]=a[rpos++];while(lpos<=leftn)/*copyrestofthefirstpart*/tmp_array[tmpos++]=a[lpos++];while(rpos<=rightn)/*copyrestofthesecondpart*/tmp_array[tmpos++]=a[rpos++];/*copyarrayback*/for(i=0;i<num_elements;i++,rightn--)a[rightn]=tmp_array[rightn];}-voidmsort(inta[],inttmp_array[],intleft,intright){-intcenter;if(left<right)ifcenter=(right+left)/2;msort(a,tmp_array,left,center);msort(a,tmp_array,center+1,right);merge(a,tmp_array,left,center+1,right);}voidmerge_sort(inta[],intn){-int*tmp_array;tmp_array=(int*)malloc(n*sizeof(int));if(tmp_array!=NULL){-msort(a,tmp_array,0,n-1);free(tmp_array);}-elseprintf("Nospacefortmparray!'n");}4)插入排序基本思想是：将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数增1的有序表：C++Code1voidInsertionSort(intarr[],intnum)2{3inttemp;4inti,j;5for(i=1;i<num;i++)6{7temp=arr[i];8for(j=i;j>0&&arr[j-1]>temp;j--)9arr[j]=arr[j-1];10arr[j]=temp;11}}(5)冒泡排序/*冒泡排序时间复杂度最好的情况为O(n),最坏的情况是O(nT)*基本思想是:两两比较相邻记录的关键字,如果反序则交换*/C++Code1voidBubbleSort1(intarr[],intnum)2{3inti,j;4for(i=0;i<num;i++)5{

6for(j=1;j<num--i；j++)7{8if(arr[j-1]>arr[j])9swap1(&arr[j-1],&arr[j]);10}11}}(1)MergeTwoSortedLists两条有序链表排序，单链表排序一般采用归并排序效率比较高C++Code1//LeetCode,MergeTwoSortedLists2//时间复杂度O(min(m,n))，空间复杂度0(1)3classSolution4{5public:6ListNode*mergeTwoLists(ListNode*l1,ListNode*l2)7{8if(l1==nullptr)returnl2;9if(l2==nullptr)returnl1;10ListNodedummy(-1);11ListNode*p=&dummy;12for(;l1!=nullptr&&l2!=nullptr;p=p->next13)14{15if(l1->val>l2->val)16{17p->next=l2;18l2=l2->next;19}20else21{22p->next=l1;23l1=l1->next;24}25}26p->next=l1!=nullptr?l1:l2;27returndummy.next;28}｝；(2)SortList，对一个链表进行排序常数空间且O(nlogn)，单链表适合用归并排序，双向链表适合用快速排序。本题可以复用”MergeTwoSortedLists”的代码。

123456789101112131415161718192021222324252627C++Code//LeetCode,SortList//归并排序，时间复杂度0(nlogn),空间复杂度0(1)classSolution{public:ListNode*sortList(ListNode*head){if(head==NULL||head-〉next==NULL)returnhead;//快慢指针找到中间节点ListNode*fast=head,*slow=head;while(fast->next!=NULL&&fast->next->next!=NULL){fast=fast->next->next;slow=slow->next;}//断开fast=slow;slow=slow->next;fast->next=NULL;ListNode*l1=sortList(head);//前半段排序ListNode*l2=sortList(slow);//后半段排序returnmergeTwoLists(l1,l2);}//MergeTwoSortedListsListNode*mergeTwoLists(ListNode*l1,ListNode*l2){ListNodedummy(-1);for(ListNode*p=&dummy;l1!=nullptr||l2!=nullptr;p=p->next){intval1=l1==nullptr?INT_MAX:l1->val;intval2=l2==nullptr?INT_MAX:l2->val;if(val1<=val2){p->next=l1;=l1->next;}else{p->next=l2;=l2->next;}

};}9、深度搜索10.12.1适用场景输入数据：如果是递归数据结构，如单链表，二叉树，集合，则百分之百可以用深搜；如果是非递归数据结构，如一维数组，二维数组，字符串，图，则概率小一些。状态转换图：树或者图。求解目标：必须要走到最深（例如对于树，必须要走到叶子节点）才能得到一个解，这种情况适合用深搜。主要考虑好剪枝条件。/////题目：abc全排列abcacbbacbcacabcba六种Givenacollectionofnumbers,returnallpossiblepermutations.Forexample,havethefollowingpermutations:,[1,3,2],[2,1,3],[2,3,1],[3,1,2],and[3,2,1].12341234567891011121314{public:vector<vector<int>>p