算法大全单链表算法大全(1)单链表

《算法大全单链表算法大全(1)单链表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法大全单链表:算法大全(1)单链表疯狂代码http://CrazyCoder.cn/ĵ:http:/CrazyCoder.cn/BlogDigest/Article78252.html声明本文所有13道算法题目覆盖了基本上所有常见单链表问题全都用C#实现并测试通过代码下载:TestLink.zip1.单链表反转2.找出单链表倒数第4个元素3.找出单链表中间元素4.删除无头单链表个节点5.两个不交叉有序链表合并6.有个2级单链表其中每个元素都含有个指向个单链表指针写把这个2级链表称级单链表7.单链表交换任意两个元素(不包括表头)8.判断单链表是否有环？如何找到环“起始”点？如何知道环长

2、度？9.判断两个单链表是否相交10.两个单链表相交计算相交点11.用链表模拟大整数加法运算12.单链表排序13.删除单链表中重复元素首先写个单链表C#实现这是我们基石:publicLink{publicLinkNext;publicData;publicLink(Linknext,data){this.Next=next;this.Data=data;}}其中我们需要人为地在单链表前面加个空节点称其为head例如个单链表是1->2->5如图所示:对个单链表遍历如下所示:voidMain(args){Linkhead=GenerateLink;Linkcurr=head;while(cu

3、rr!=null){Console.WriteLine(curr.Data);curr=curr.Next;}}1.单链表反转这道题目有两种算法既然是要反转那么肯定是要破坏原有数据结构:算法1:我们需要额外两个变量来存储当前节点curr下个节点next、再下个节点nextnext:publicLinkReverseLink1(Linkhead){Linkcurr=head.Next;Linknext=null;Linknextnext=null;//noelementsor_disibledevent=>(currnull

4、

5、curr.Nextnull){head;}//moretha

6、n_disibledevent=>while(curr.Next!=null){next=curr.Next;//1nextnext=next.Next;//2next.Next=head.Next;//3head.Next=next;//4curr.Next=nextnext;//5}head;}算法核心是while循环中5句话画个图来表示这5个步骤:我们发现curr始终指向第1个元素此外出于编程严谨性还要考虑2种极特殊情况:没有元素单链表以及只有个元素单链表都是不需要反转算法2:自然是递归如果题目简化为逆序输出这个单链表那么递归是很简单在递归的后输出当前元素这样能确保输出第N个元素

7、语句永远在第N+1个递归的后执行也就是说第N个元素永远在第N+1个元素的后输出最终我们先输出最后个元素然后是倒数第2个、倒数第3个直到输出第1个:publicvoidReverseLink2(Linkhead){(head.Next!=null){ReverseLink2(head.Next);Console.WriteLine(head.Next.Data);}}但是现实应用中往往不是要求我们逆序输出(不损坏原有单链表)而是把这个单链表逆序(破坏型)这就要求我们在递归时候还要处理递归后逻辑首先要把判断单链表有0或1个元素这部分逻辑独立出来而不需要在递归中每次都比较次:publicLi

8、nkReverseLink3(Linkhead){//noelementsor_disibledevent=>(head.Nextnull

9、

10、head.Next.Nextnull)head;head.Next=ReverseLink(head.Next);head;}我们观测到:head.Next=ReverseLink(head.Next);这句话意思是为ReverseLink思路方法生成逆序链表添加个空表头接下来就是递归核心算法ReverseLink了:LinkReverseLink(Linkhead){(head.Nextnull)head;LinkrHead=ReverseLi

11、nk(head.Next);head.Next.Next=head;head.Next=null;rHead;}算法关键就在于递归后两条语句:head.Next.Next=head;//1head.Next=null;//2啥意思呢？画个图表示就是:这样就得到了个逆序单链表我们只用到了1个额外变量rHead2.找出单链表倒数第4个元素这道题目有两种算法但无论哪种算法都要考虑单链表少于4个元素情况:第1种算法建立两个指针第个先走4步然后第2个指针