推荐学习

文章简述

不过没关系，从本文分享的算法问题会把关于这个问题的代码全部写出来，以debug的形式分解每一步来整理。

通过还原题目场景，调试分析，印象更加深刻。

本文有三个主题。

一，合并两个有序链表

1.1题目分析

或者循环两个链表，然后比较它们，就像：

For () {for () {if () {}}好吧，其实这个问题的本质就是可以用递归，这个。画一个草图，简单描述一下。

第一步：

比较两个链表的第一个节点。

如果两个节点相等，则将L2链表[1]与L1链表[2]进行比较。

注意：

在L1节点[1]和L2节点[1]之间的比较完成之后，1.next指针需要被修改以指向它的下一个节点。

第二步：

现在我们有了L2链表[1]，它的下一个指针指向谁呢？即L2链表[1]与L1链表[2]相比较。

经过比较，L2链表[1]的下一个指向L1链表[2]，以此类推。

L2列表[3]与L1列表[4]进行了比较。

最后，将L1链表与L2链表进行了比较。

所有的比较完成后，整个链表就排序好了。

递归的方式是每两个节点进行比较。当一个链表为空时，意味着其中一个链表已经被遍历，所以需要终止递归，返回比较结果。

可能只是一个简单的不太好理解的图。下面用代码调试的方式分析一下，请耐心等待。

1.2代码分析

ClassListNode{intval；listnode Next；ListNode(){ } ListNode(intval){ this . val=val；}ListNode(intval，ListNode next){ this . val=val；this.next=next} @ OverridepublicStringtoString(){ return ' listnode { ' ' val=' val ' } '}}定义添加链表的方法。

publillistnodeadd(listnode node){//1，定义辅助指针ListNodetemp=nodeHead//2、首先判断当前节点是否是最后一个节点if(null==temp.next){//当前节点是最后一个节点temp.next=nodereturnnodeHead}//3，遍历节点。如果当前节点的下一个节点不为空，则表示有后续节点while(null！=temp.next){//否则将指针移回temp=temp.next}//4、遍历结束时，将最后一个节点的指针指向新添加的节点temp.next=nodereturnnodeHead.next}然后创建2个链表。

list nodel 11=new list node(1)；list node 12=new list node(2)；list node 13=new list node(4)；mergelinkedlist 1=newMergeLinkedList()；L1 . add(l11)；L1 . add(l12)；listnodeadd 1=L1 . add(l13)；list nodel 21=new list node(1)；listnode 122=new listnode(3)；listnode 123=new listnode(4)；mergelinkedlist 2=newMergeLinkedList()；L2 . add(l21)；L2 . add(l22)；listnode add 2=L2 . add(l23)；先贴上图中使用递归的代码。

publicllistnode generatewolists(listnode L1，listnode L2) {If(L1==null){ return L2；}if(l2==null){ret

1.3debug调试

1.3.1L1链表已经创建完成，同理L2也被创建完成。

1.3.2比较两个链表的首节点

注意：

l1.next是指向递归方法的，也就是上图中我们描述的l1链表【1】指向了l2链表【1】，但是L2链表【1】又指向谁？开始进入递归

1.3.3如上图，开始比较L2链表【1】与L1链表的【2】

1.3.4比较L1链表【2】与L2链表【3】

1.3.5后面操作是一样的，下面就直接展示最后两个节点比较

这里已经到最后两个节点的比较。

这个时候L1链表先遍历完成，需要终止递归，返回L2链表。为什么返回L2链表？直接看图。

因为最后一步比较的是L1链表【4】和L2链表【4】，也就是说L2链表【4】是最后的节点，如果返回L1链表，那L2链表【4】就会被丢弃，可参考上面图解的最后一张。

重点来了！！！

重点来了！！！

重点来了！！！

L1链表已经遍历完成，开始触发递归将比较的结果逐次返回。

这是不是我们最后L1链表【4】和L2链表【4】比较的那一步，是不是很明显，l1.next指向了l1的节点【4】，而L1节点也就是它最后的节点【4】，和我们那上面图解中最后的结论一样。

再接着执行下一步返回。

L2链表的【3】指向了L1链表的【4】

同理，按照之前递归的结果以此返回就可以了，那我们来看下最终的排序结果。

二，删除排序链表中的重复元素

2.1题目分析

初次看这道题好像挺简单的，这不就是个人之前写的第一篇文章里面，删除链表节点吗！

仔细审题其实这道题要更简单些，因为题中已说明是一个排序链表，因此我们只需要将当前节点与下一个节点进行比较，如果相等则直接修改next指针即可。

2.1代码分析

同样是链表的定义，与上面第一题中的创建是一样的，只不过我们是需要再重新创建一个单链表。

ListNodel1=newListNode(1);ListNodel2=newListNode(1);ListNodel3=newListNode(3);ListNodel4=newListNode(4);ListNodel5=newListNode(4);ListNodel6=newListNode(5);NodeFunnodeFun=newNodeFun();nodeFun.add(l1);nodeFun.add(l2);nodeFun.add(l3);nodeFun.add(l4);nodeFun.add(l5);ListNodelistNode=nodeFun.add(l6);

创建完成后，接着看去重复的代码。

publicListNodedeleteDuplicates(ListNodehead){/***定义辅助指针*/ListNodetemp=head;/***判断当前节点和下一个节点不能为空，因为是需要将当前节点和下一个节点进行比较的*/while(temp!=null&&temp.next!=null){/***如果节点值相同*/if(temp.val==temp.next.val){/***表示当前节点与下一个节点的值相同，则移动指针*/temp.next=temp.next.next;}else{/***必须移动指针，否则会产生死循环*/temp=temp.next;}}returnhead;}}

2.2debug调试

2.2.1按照初始化的链表，应该是首节点【1】和第二个节点【1】进行比较。

不用说两个节点是相等的，那下一步进入if判断，就是修改指针的指向。

此时第二个节点【1】已经没有被next指引了，就会被GC回收掉。

2.2.2下一步就是节点【1】和节点【3】进行比较

两个节点不相等，进入else将辅助指针移动到下个节点。

那么剩下的节点判断也都是一样的，我们最后看下打印的结果。

三，环形链表

3.1题目分析

如果这个链表里面有环，其中一个节点必然是被指针指引了一次或者多次（如果有多个环的话）。因此个人当时简单的做法就是遍历链表，把遍历过的节点对象保存到HashSet中，每遍历下一个节点时去HashSet中比对，存在就表示有环。

而这道题没有设置过多的要求，只要有环返回boolean就好。

还有一种巧妙的写法，使用快慢指针的思想。

这种方式大致意思就是说，快慢指针比作龟兔赛跑，兔子跑的快，如果存在环那么兔子就会比乌龟先跑进环中。那么它们就会在某个节点上相遇，相遇了也就说明链表是有环的。

那么，你们问题是不是来了？这不公平啊，【兔子】本来就比【乌龟】跑的快，那咋兔子还先跑了。

试想，如果它俩都在一个节点上跑，那它们从开始不就是相遇了，因为我们我们是设定如果在一个节点上相遇，表示链表是有环的。所以，这不是“不打自招“了！

比赛开始，这【兔子大哥】有点猛啊，一下跑两个节点。

果然，有情人终成眷属，它们相遇了。

3.2代码分析

这次创建链表的时候，就不能单纯是个单链表了，还得加个环。

ListNodel1=newListNode(3);ListNodel2=newListNode(2);ListNodel3=newListNode(0);ListNodel4=newListNode(-4);/***给主角加个环*/l4.next=l2;NodeFunnodeFun=newNodeFun();nodeFun.add(l1);nodeFun.add(l2);nodeFun.add(l3);ListNodelistNode=nodeFun.add(l4);

那就一起来找环吧。

publicbooleanhasCycle(ListNodehead){ListNodetemp=head;if(null==head){//为空表示没有环returnfalse;}//1，set集合保存遍历过的节点，如果新的节点已经在set中，表示存在环//2，使用快慢指针的思想//定义慢指针ListNodeslow=head;//定义快指针ListNodefast=head.next;//循环，只要2个指针不重合，就一直循环while(slow!=fast){//如果2个指针都到达尾节点，表示没有环if(fast==null||fast.next==null){returnfalse;}//否则就移动指针slow=slow.next;fast=fast.next.next;}returntrue;}

3.3debug调试

所以，尴尬的事情来了，这玩意debug不了啊。如果存在环，那么while循环是不会进来的。

那就直接看下结果吧。

如果把环去掉就是？

那还用猜？没有光环了肯定。。。

作者：奋进的小样

原文链接：https://www.cnblogs.com/fenjyang/p/14426665.html