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

《算法大全-面试题-数据结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、单链表目录1.单链表反转2.找出单链表的倒数第4个元素3.找出单链表的中间元素4.删除无头单链表的一个节点5.两个不交叉的有序链表的合并6.有个二级单链表，其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级链表称一级单链表。7.单链表交换任意两个元素（不包括表头）8.判断单链表是否有环？如何找到环的“起始”点？如何知道环的长度？9.判断两个单链表是否相交10.两个单链表相交，计算相交点11.用链表模拟大整数加法运算12.单链表排序13.删除单链表中重复的元素首先写一个单链表的C#实现，这是我们的基石：publicclassLink{publicLinkNe

2、xt;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.单链表反

3、转这道题目有两种算法，既然是要反转，那么肯定是要破坏原有的数据结构的：算法1：我们需要额外的两个变量来存储当前节点curr的下一个节点next、再下一个节点nextnext：publicstaticLinkReverseLink1(Linkhead){Linkcurr=head.Next;Linknext=null;Linknextnext=null;//ifnoelementsoronlyoneelementexistsif(curr==null

4、

5、curr.Next==null){returnhead;}//ifmorethanoneelementwhile(cur

6、r.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个元素语句永

7、远在第N+1个递归函数之后执行，也就是说第N个元素永远在第N+1个元素之后输出，最终我们先输出最后一个元素，然后是倒数第2个、倒数第3个，直到输出第1个：publicstaticvoidReverseLink2(Linkhead){if(head.Next!=null){ReverseLink2(head.Next);Console.WriteLine(head.Next.Data);}}但是，现实应用中往往不是要求我们逆序输出（不损坏原有的单链表），而是把这个单链表逆序（破坏型）。这就要求我们在递归的时候，还要处理递归后的逻辑。首先，要把判断单链表有0或1个元素这部分

8、逻辑独立出来，而不需要在递归中每次都比较一次：publicstaticLinkReverseLink3(Linkhead){//ifnoelementsoronlyoneelementexistsif(head.Next==null

9、

10、head.Next.Next==null)returnhead;head.Next=ReverseLink(head.Next);returnhead;}我们观测到：head.Next=ReverseLink(head.Next);这句话的意思是为ReverseLink方法生成的逆序链表添加一个空表头。接下来就是递归的核心算法Revers

11、eLink了：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个元素这