2020年数据结构算法面试大全.docx

2020年最新数据构造算法面试大全 一、单链表 目录 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; //ifnoelementsoronlyoneelementexists if(curr==null||curr.Next==null) { returnhead; } //ifmorethanoneelement while(curr.Next!=null) { next=curr.Next;nextnext=next.Next;next.Next=head.Next;head.Next=next;curr.Next=nextnext;  //1 //2 //3 //4 //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) { //ifnoelementsoronlyoneelementexists if(head.Next==null||==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; head.Next=null; returnrHead