Java实现单链表的各种操作
主要内容:
- 单链表的基本操作
- 删除重复数据
- 找到倒数第k个元素
- 实现链表的反转
- 从尾到头输出链表
- 找到中间节点
- 检测链表是否有环
- 在不知道头指针的情况下删除指定节点
- 如何判断两个链表是否相交并找出相交节点
直接上代码,就是这么奔放~~~
packagepers.ty.$1101datastructure; importjava.util.Hashtable; /** *@authorAdministrator *实现单链表的基本操作,增加删除节点、排序、打印、计算长度 */ publicclassMyLinkedList{ Nodehead=null;//链表头的作用 /**向链表中插入数据 *@paramd:插入数据的内容 */ publicvoidaddNode(intd){ NodenewNode=newNode(d); if(head==null){ head=newNode; return; } Nodetmp=head; while(tmp.next!=null){ tmp=tmp.next; } //addNodetoend tmp.next=newNode; } /** *@paramindex:删除第index个节点 *@return成功返回true,失败返回false */ publicBooleandeleteNode(intindex){ if(index<1||index>length()){ returnfalse;//删除元素位置不合理 } //删除链表中的第一个元素 if(index==1){ head=head.next; returntrue; } inti=1; NodepreNode=head; NodecurNode=preNode.next; while(curNode!=null){ if(i==index){ preNode.next=curNode.next; returntrue; } preNode=curNode; curNode=curNode.next; i++; } returntrue; } /** *@return返回链表的长度length */ publicintlength(){ intlength=0; Nodetmp=head; while(tmp!=null){ length++; tmp=tmp.next; } returnlength; } /** *对链表进行排序 *@return返回排序后的头结点 */ publicNodeorderList(){ NodenextNode=null; inttemp=0; NodecurNode=head; while(curNode.next!=null){ nextNode=curNode.next; while(nextNode!=null){ if(curNode.data>nextNode.data){ temp=curNode.data; curNode.data=nextNode.data; nextNode.data=temp; } nextNode=nextNode.next; } curNode=curNode.next; } returnhead; } /** *打印链表中所有数据 */ publicvoidprintList(){ Nodetmp=head; while(tmp!=null){ System.out.print(tmp.data+""); tmp=tmp.next; } System.out.println(); } /** *从链表中删除数据的第一种方法 *遍历链表,把遍历到的数据存到一个Hashtable中,在遍历过程中若当前访问的值在Hashtable *中存在,则可以删除 *优点:时间复杂度低缺点:需要额外的存储空间来保存已访问过得数据 */ publicvoiddeleteDuplecate1(){ Hashtable<Integer,Integer>table=newHashtable<Integer,Integer>(); Nodetmp=head; Nodepre=null; while(tmp!=null){ if(table.containsKey(tmp.data)) pre.next=tmp.next; else{ table.put(tmp.data,1); pre=tmp; } tmp=tmp.next; } } /** *从链表中删除重复数据的第二种方法 *双重循环遍历 *优缺点很明显 */ publicvoiddeleteDuplecate2(){ Nodep=head; while(p!=null){ Nodeq=p; while(q.next!=null){ if(p.data==q.next.data){ q.next=q.next.next; }else{ q=q.next; } } p=p.next; } } /** *@paramk:找到链表中倒数第k个节点 *@return该节点 *设置两个指针p1、p2,让p2比p1快k个节点,同时向后遍历,当p2为空,则p1为倒数第k个节点 */ publicNodefindElem(Nodehead,intk){ if(k<1||k>this.length()) returnnull; Nodep1=head; Nodep2=head; for(inti=0;i<k-1;i++) p2=p2.next; while(p2.next!=null){ p2=p2.next; p1=p1.next; } returnp1; } /** *实现链表的反转 *@paramhead链表的头节点 */ publicvoidreverseIteratively(Nodehead){ NodepReversedHead=head; NodepNode=head; NodepPrev=null; while(pNode!=null){ NodepNext=pNode.next; if(pNext==null) pReversedHead=pNode; pNode.next=pPrev; pPrev=pNode; pNode=pNext; } this.head=pReversedHead; } /** *通过递归从尾到头输出单链表 *@paramhead */ publicvoidprintListReversely(Nodehead){ if(head!=null){ printListReversely(head.next); System.out.print(head.data+""); } } /** *查询单链表的中间节点 *定义两个指针,一个每次走一步,一个每次走两步... *@paramhead *@returnq为中间节点 */ publicNodesearchMid(Nodehead){ Nodeq=head; Nodep=head; while(p!=null&&p.next!=null&&p.next.next!=null){ q=q.next; p=p.next.next; } returnq; } /** *在不知道头指针的情况下删除指定节点 *链表尾节点无法删除,因为删除后无法使其前驱节点的next指针置为空 *其他节点,可以通过交换这个节点与其后继节点的值,然后删除后继节点 *@paramn *@return */ publicbooleandeleteNode(Noden){ if(n==null||n.next==null) returnfalse; inttmp=n.data; n.data=n.next.data; n.next.data=tmp; n.next=n.next.next; returntrue; } /** *判断两个链表是否相交 *如果两个链表相交,则肯定有相同的尾节点,遍历两个链表,记录尾节点,看是否相同 *@paramh1链表1的头节点 *@paramh2链表2的头结点 *@return是否相交 */ publicbooleanisIntersect(Nodeh1,Nodeh2){ if(h1==null||h2==null) returnfalse; Nodetail1=h1; while(tail1.next!=null){ tail1=tail1.next; } Nodetail2=h2; while(tail2.next!=null){ tail2=tail2.next; } returntail1==tail2; } /** *找出相交的第一个节点 *@paramh1 *@paramh2 *@return */ publicNodegetFirstMeetNode(Nodeh1,Nodeh2){ if(h1==null||h2==null) returnnull; Nodetail1=h1; intlen1=1; while(tail1.next!=null){ tail1=tail1.next; len1++; } Nodetail2=h2; intlen2=1; while(tail2.next!=null){ tail2=tail2.next; len2++; } if(tail1!=tail2){ returnnull; } Nodet1=h1; Nodet2=h2; //找出较长的链表先遍历 if(len1>len2){ intd=len1-len2; while(d!=0){ t1=t1.next; d--; } } if(len1<len2){ intd=len2-len1; while(d!=0){ t2=t2.next; d--; } } while(t1!=t2){ t1=t1.next; t2=t2.next; } returnt1; } publicstaticvoidmain(String[]args){ MyLinkedListlist=newMyLinkedList(); } }
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持毛票票!