java数据结构—单链表的实现原理

再次学习数据额结构，看到前面的单链表，感觉里面的思路很不错,自己动手写代码尝试一下，果然一动手就发现自己并没有完全理解。这里主要记录我花了很长时间才理解的地方，不去考虑增删改查，我觉得这些功能在很多地方都实现过，不是重点，也有很多资料可查。

单链表的原理网上很多，这里也不解释，先上代码。

这是一个节点类，用于记录节点内容和对象引用（地址），其中不包含一些基本功能，只写了必要的函数。

public class Node { Object data;//节点包含的具体内容 Node next;//节点的引用，用于指向下一个节点 Node (Node i){//构造函数1，用于初始化头结点 next=i; } Node (Object i,Node j){//构造函数2，用于其他节点。 data=i; next=j; } public void setnext(Node nextval){//这个函数作用是把其他节点的引用指向这个节点。 next=nextval; } public Object getelement(){//获取节点的内容 return data; } }

这是我第一次做的测试函数

public class main_Node { public static void main(String[] args) { Node head;//头结点 Node current;//表示当前节点 current=head=new Node(null);//初始化为空 current.setnext(new Node(1,head.next));//添加一个节点 current.setnext(new Node(2,current.next));//添加两个节点 current.setnext(new Node(3,current.next));//添加三个节点 current=head.next;//让current表示head的下一个节点，也就是第一个节点。 int a=(int)current.getelement();//获取该节点的内容 System.out.println(a);//打印 } }

结果为3，这里就有问题了，我命名让他指向第一个节点，应该是1才对呀，怎么会变成第三个呢？debug的结果是这样的：：

可以看出来，这里的head直接指向的是3，刚好反过来了，所以刚才得出的值是3。

看似很简单的问题，我还是花了很长时间才发现问题。其实原因是这样添加节点时，current所指向的节点并没有变，还是在头结点位置，添加节点并不能使current表示的节点后移，所以解决办法是在每次添加了新的节点后把current往后移一下，让它指向新添加的节点，这样才能在新添加的节点后面再添加节点。代码如下：

public class main_test1 { public static void main(String[] args) { test1 head; test1 current; current=head=new test1(null);//这里也表示current指向头结点 current.setnext(new test1(1,head.next)); current=current.next;//使current指向下一个节点 current.setnext(new test1(2,current.next)); current=current.next; current.setnext(new test1(3,current.next)); current=current.next; current=head.next; int a=(int)current.getelement(); System.out.println(a); } }

结果为1。这次正确了，再看debug图： 看，这下顺序就对了。 这里主要的问题是，没有想到添加新节点后想在其后面继续添加，是要先移动当前current所指向的节点的位置的。感觉以后这个思路会给我帮助，记录下来方便以后复习。

补充：一个单链表的优秀技巧贴：http://wuchong.me/blog/2014/03/25/interview-link-questions/

对这篇博客的一些地方做一些补充，记录自己思考的结果： 第八点：链表有环，如何判断相交： 我自己想了另一种方法，应该比博客中的效率高一点，其实也是借鉴了上面的思想，设置三个节点，其中一快一慢（和前面的一个意思，快的前进两格）指向head1,另一个快指向head2。这里思路是：如果两个有环链表相交（这里不考虑两个无环链表相交的情况），那么当前面设置的三个节点都进入环中的时候，就可以利用head2_fast去追赶head1_low,这里最关键的地方是考虑什么时候停止追赶，因为环内是可以无限循环的。仔细琢磨第5点的原理就能找到关键点了，看代码理解吧：

public boolean isIntersect(Node head1,Node head2){ //设置三个节点 Node head1_low=head1; Node head1_fast=head1; Node head2_fast=head2; while(head1_fast!=null && head1_fast.next!=null && head2_fast!=null && head2_fast.next!=null){//如果有无环链表直接判断不相交 head1_low=head1_low.next; head1_fast=head1_fast.next.next; head2_fast=head2_fast.next.next; if(head1_low==head2_fast)//过程中如果运气好，可以直接得到相交 return true; else if(head1_low==head1_fast){//核心，也就是找到慢指针和快指针相交的点后就进行head2_fast追赶head1_low do{//这里有个问题，如果head2除了环之外的部分特别长，那么这里是不成立的，就需要设立第四个节点，后面给出 head1_low=head1_low.next; head2_fast=head2_fast.next.next; if(head1_low==head2_fast) return true; }while(head1_low.next!=head1_fast);//如果相交，head1_low跑一圈内必然能够相等。 return false; } } return false; }

给出上面的修正代码，其实就是要确认开始追赶时head2_fast已经进入环内，不然会出现head1_low跑完一圈head2_fast还未进环的情况，同样通过给head2_fast也找个相交点来判断是否进环：

public boolean isIntersect(Node head1,Node head2){ Node head1_low=head1; Node head1_fast=head1; Node head2_low=head2; Node head2_fast=head2; while(head1_fast!=null && head1_fast.next!=null && head2_fast!=null && head2_fast.next!=null){ head1_low=head1_low.next; head1_fast=head1_fast.next.next; head2_low=head1_low.next; head2_fast=head2_fast.next.next; if(head1_low==head2_fast) return true; else if(head1_low==head1_fast){ while(head2_low!=head2_fast){ head2_low=head1_low.next; head2_fast=head2_fast.next.next; if(head2_fast!=null && head2_fast.next!=null) return false; } do{ head1_low=head1_low.next; head2_fast=head2_fast.next.next; if(head1_low==head2_fast) return true; }while(head1_low.next!=head1_fast); return false; } else if(head2_low==head2_fast){ while(head1_low!=head1_fast){ head1_low=head1_low.next; head1_fast=head1_fast.next.next; if(head1_fast!=null && head1_fast.next!=null) return false; } do{ head1_low=head1_low.next; head2_fast=head2_fast.next.next; if(head1_low==head2_fast) return true; }while(head1_low.next!=head1_fast); return false; } } return false; }

其实变化不大，看一看就明白，不过这样一来和原方法比较优势就不明显了。总之提供一种思路吧（以上方法没有经过检验，可能有瑕疵）。

第九点：两链表相交的第一个公共节点： 博主没有写这种方法，也许是他觉得没必要，因为所有东西博客上都提到了，有心人应该是自己能推理出来的： 把一个链表接到另一个链表的尾部，形成环，再用判断环的入口，就ok了。是不是所有东西博客里都有写到？