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();
}
}
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持毛票票！