算法大全-数据结构 -面试题

1常用的等式：-n=~(n-1)=~n+12获取整数n的二进制中最后一个1：n&(-n)或者n&~(n-1)，如：n=010100，则-n=101100，n&(-n)=0001003去掉整数n的二进制中最后一个1：n&(n-1)，如：n=010100，n-1=010011，n&(n-1)=010000（PS：常用于检查一个数的二进制中有多少个1，我记得小米面试的时候考过我，我当时没用位运算，显得很笨很蠢哈，要考虑很多情况，希望有看到这个博客的朋友再去小米，直接秒杀之）。一、单链表目录1.单链表反转2.找出单链表的倒数第4个元素3.找出单链表的中间元素4.删除无头单链表的一个节点5.两个不交叉的有序链表的合并6.有个二级单链表，其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级链表称一级单链表。7.单链表交换任意两个元素（不包括表头）8.判断单链表是否有环？如何找到环的“起始”点？如何知道环的长度？9.判断两个单链表是否相交10.两个单链表相交，计算相交点11.用链表模拟大整数加法运算12.单链表排序13.删除单链表中重复的元素首先写一个单链表的C#实现，这是我们的基石：publicclassLink{publicLinkNext;publicstringData;publicLink(Linknext,stringdata){this.Next=next;this.Data=data;}}其中，我们需要人为地在单链表前面加一个空节点，称其为head。例如，一个单链表是1-2-5，如图所示：对一个单链表的遍历如下所示：staticvoidMain(string[]args){Linkhead=GenerateLink();Linkcurr=head;while(curr!=null){Console.WriteLine(curr.Data);curr=curr.Next;}}1.单链表反转这道题目有两种算法，既然是要反转，那么肯定是要破坏原有的数据结构的：算法1：我们需要额外的两个变量来存储当前节点curr的下一个节点next、再下一个节点nextnext：publicstaticLinkReverseLink1(Linkhead){Linkcurr=head.Next;Linknext=null;Linknextnext=null;//ifnoelementsoronlyoneelementexistsif(curr==null||curr.Next==null){returnhead;}//ifmorethanoneelementwhile(curr.Next!=null){next=curr.Next;//1nextnext=next.Next;//2next.Next=head.Next;//3head.Next=next;//4curr.Next=nextnext;//5}returnhead;}算法的核心是while循环中的5句话我们发现，curr始终指向第1个元素。此外，出于编程的严谨性，还要考虑2种极特殊的情况：没有元素的单链表，以及只有一个元素的单链表，都是不需要反转的。算法2：自然是递归如果题目简化为逆序输出这个单链表，那么递归是很简单的，在递归函数之后输出当前元素，这样能确保输出第N个元素语句永远在第N+1个递归函数之后执行，也就是说第N个元素永远在第N+1个元素之后输出，最终我们先输出最后一个元素，然后是倒数第2个、倒数第3个，直到输出第1个：publicstaticvoidReverseLink2(Linkhead){if(head.Next!=null){ReverseLink2(head.Next);Console.WriteLine(head.Next.Data);}}但是，现实应用中往往不是要求我们逆序输出（不损坏原有的单链表），而是把这个单链表逆序（破坏型）。这就要求我们在递归的时候，还要处理递归后的逻辑。首先，要把判断单链表有0或1个元素这部分逻辑独立出来，而不需要在递归中每次都比较一次：publicstaticLinkReverseLink3(Linkhead){//ifnoelementsoronlyoneelementexistsif(head.Next==null||head.Next.Next==null)returnhead;head.Next=ReverseLink(head.Next);returnhead;}我们观测到：head.Next=ReverseLink(head.Next);这句话的意思是为ReverseLink方法生成的逆序链表添加一个空表头。接下来就是递归的核心算法ReverseLink了：staticLinkReverseLink(Linkhead){if(head.Next==null)returnhead;LinkrHead=ReverseLink(head.Next);head.Next.Next=head;head.Next=null;returnrHead;}算法的关键就在于递归后的两条语句：head.Next.Next=head;//1head.Next=null;//2啥意思呢？画个图表示就是：这样，就得到了一个逆序的单链表，我们只用到了1个额外的变量rHead。2.找出单链表的倒数第4个元素这道题目有两种算法，但无论哪种算法，都要考虑单链表少于4个元素的情况：第1种算法，建立两个指针，第一个先走4步，然后第2个指针也开始走，两个指针步伐（前进速度）一致。staticLinkGetLast4thOne(Linkhead){Linkfirst=head;Linksecond=head;for(inti=0;i4;i++){if(first.Next==null)thrownewException(Lessthan4elements);first=first.Next;}while(first!=null){first=first.Next;second=second.Next;}returnsecond;}第2种算法，做一个数组arr[4]，让我们遍历单链表，把第0个、第4个、第8个……第4N个扔到arr[0]，把第1个、第5个、第9个……第4N+1个扔到arr[1]，把第2个、第6个、第10个……第4N+2个扔到arr[2]，把第3个、第7个、第11个……第4N+3个扔到arr[3]，这样随着单链表的遍历结束，arr中存储的就是单链表的最后4个元素，找到最后一个元素对应的arr[i]，让k=(i+1)%4，则arr[k]就是倒数第4个元素。staticLinkGetLast4thOneByArray(Linkhead){Linkcurr=head;inti=0;Link[]arr=newLink[4];while(curr.Next!=null){arr[i]=curr.Next;curr=curr.Next;i=(i+1)%4;}if(arr[i]==null)thrownewException(Lessthan4elements);returnarr[i];}本题目源代码下载：推而广之，对倒数第K个元素，都能用以上2种算法找出来。3.找出单链表的中间元素算法思想：类似于上题，还是使用两个指针first和second，只是first每次走一步，second每次走两步：staticLinkGetMiddleOne(Linkhead){Linkfirst=head;Linksecond=head;while(first!=null&&first.Next!=null){first=first.Next.Next;second=second.Next;}returnsecond;}但是，这道题目有个地方需要注意，就是对于链表元素个数为奇数，以上算法成立。如果链表元素个数为偶数，那么在返回second的同时，还要返回second.Next也就是下一个元素，它俩都算是单链表的中间元素。下面是加强版的算法，无论奇数偶数，一概通杀：staticvoidMain(string[]args){Linkhead=GenerateLink();boolisOdd=true;Linkmiddle=GetMiddleOne(head,refisOdd);if(isOdd){Console.WriteLine(middle.Data);}else{Console.WriteLine(middle.Data);Console.WriteLine(middle.Next.Data);}Console.Read();}staticLinkGetMiddleOne(Linkhead,refboolisOdd){Linkfirst=head;Linksecond=head;while(first!=null&&first.Next!=null){first=first.Next.Next;second=second.Next;}if(first!=null)isOdd=false;returnsecond;}4.一个单链表，很长，遍历一遍很慢，我们仅知道一个指向某节点的指针curr，而我们又想删除这个节点。这道题目是典型的“狸猫换太子”，如下图所示：如果不考虑任何特殊情况，代码就2行：curr.Data=curr.Next.Data;curr.Next=curr.Next.Next;上述代码由一个地方需要注意，就是如果要删除的是最后一个元素呢？那就只能从头遍历一次找到倒数第二个节点了。此外，这道题目的一个变身就是将一个环状单链表拆开（即删除其中一个元素），此时，只要使用上面那两行代码就可以了，不需要考虑表尾。相关问题：只给定单链表中某个结点p(非空结点)，在p前面插入一个结点q。话说，交换单链表任意两个节点，也可以用交换值的方法。但这样就没意思了，所以，才会有第7题霸王硬上工的做法。5.两个不交叉的有序链表的合并有两个有序链表，各自内部是有序的，但是两个链表之间是无序的。算法思路：当然是循环逐项比较两个链表了，如果一个到了头，就不比较了，直接加上去。注意，对于2个元素的Data相等（仅仅是Data相等哦，而不是相同的引用），我们可以把它视作前面的Data大于后面的Data，从而节省了算法逻辑。staticLinkMergeTwoLink(Linkhead1,Linkhead2){Linkhead=newLink(null,Int16.MinValue);Linkpre=head;Linkcurr=head.Next;Linkcurr1=head1;Linkcurr2=head2;//compareuntilonelinkruntotheendwhile(curr1.Next!=null&&curr2.Next!=null){if(curr1.Next.Datacurr2.Next.Data){curr=newLink(null,curr1.Next.Data);curr1=curr1.Next;}else{curr=newLink(null,curr2.Next.Data);curr2=curr2.Next;}pre.Next=curr;pre=pre.Next;}//ifhead1runtotheendwhile(curr1.Next!=null){curr=newLink(null,curr1.Next.Data);curr1=curr1.Next;pre.Next=curr;pre=pre.Next;}//ifhead2runtotheendwhile(curr2.Next!=null){curr=newLink(null,curr2.Next.Data);curr2=curr2.Next;pre.Next=curr;pre=pre.Next;}returnhead;}如果这两个有序链表交叉组成了Y型呢，比如说：这时我们需要先