用JAVA实现单链表，检测字符串是否是回文串

2023-07-10 18:43:03 184

一.需求

使用JAVA实现单链表，使用单链表检测字符串是否是回文串

二.需求分析

回文串最重要的就是对称，那么最重要的问题就是找到那个中心，用快指针每步走两格，当他到达链表末端的时候，慢指针刚好到达中心，慢指针在遍历过程中（快指针到达末端时）把走过的节点进行反向操作，此时从中位点分为前后两部分，此时前半部分的指针开始往回指（取next的时候，取的是前一个节点），而慢指针继续向前，跟前半部分的数据依次进行比对，当慢指针扫完整个链表，就可以判断这是回文串，否则就提前退出，同时在前半部分往回遍历的过程中将前半部分的指针重置成正向。

链表存在奇偶数情况。

奇数的时候，快指针遍历到末端的时候，中点位即中间位置的点，此中位点下一个节点为后半部分比对开始的位置。
偶数的时候，快指针遍历到末端的时候，中点位置此时为下中位点,此中位点就是后半部分比对开始的位置。

三.代码实现

1.单链表类封装

publicclassListNode{
/**
*根节点索引位置
*/
privateintfoot;
/**
*代表链表程度
*/
privateintcount;
/**
*标识根节点
*/
privateNoderoot;

//链接点类,内部方法实现，外部使用
privateclassNode{
//数据信息
privateTdata;
//下一个节点引用
privateNodenext;

publicNode(Tdata){
this.data=data;
}

//添加节点
privatevoidadd(Tdata){
if(this.next==null){
//如果当前节点的next为null,直接创建一个新的节点
this.next=newNode(data);
}else{
//否则进行递归调用，直到最后在某个为空的节点创建一个新节点
this.next.add(data);
}
}

//删除节点1
publicvoidremove(Nodeprevious,intindex){

if(ListNode.this.foot++==index){
//this表示当前要删除的节点
previous.next=this.next;
this.next=null;
ListNode.this.count--;
return;
}else{
//递归删除
this.next.remove(this,index);
}

}

//删除节点2
publicvoidremove(Nodeprevious,Tdata){
if(this.data.equals(data)){
previous.next=this.next;
this.next=null;
ListNode.this.count--;
return;
}else{
if(this.next!=null){
this.next.remove(this,data);
}else{
return;
}
}
}

//修改数据--新数据替换旧数据
publicvoidreplace(ToldData,TnewData){
if(this.data.equals(newData)){
this.data=newData;
}else{
//递归修改，寻找当前节点下一个节点，直到某个节点的值匹配入参
this.next.replace(oldData,newData);
}

}

//修改数据--利用索引修改
publicvoidreplace(intindex,TnewData){
if(ListNode.this.foot++==index){
//找到了某个值的索引和传入的索引相同，直接替换
this.data=newData;
}else{
this.next.replace(index,newData);
}
}

//查询
publicTget(intindex){
if(ListNode.this.foot++==index){
returnthis.data;
}else{
returnthis.next.get(index);
}
}

//链表是否包含某个节点
publicbooleancontains(Tdata){
//如果当前的这个data正好和传入的data匹配
if(this.data.equals(data)){
returntrue;
}else{
//如果当前的这个不匹配，则需要查找下一个节点
if(this.next==null){
returnfalse;
}else{
returnthis.next.contains(data);
}
}
}

}

publicListNode(){

}

//检查链表是否为空
publicbooleanisEmpty(){
if(count==0||this.root==null){
returntrue;
}else{
returnfalse;
}
}

//获取链表的长度
publicintsize(){
returnthis.count;
}

//添加
publicvoidadd(Tdata){
if(this.isEmpty()){//如果链表为空，新建一个节点
this.root=newNode(data);
}else{
this.root.add(data);
}
this.count++;
}

//删除--按照索引删除
publicvoidremove(intindex){
if(this.isEmpty()){
return;
}
if(index<0||this.count<=index){
return;
}
if(index==0){//想要删除根节点
Nodetemp=this.root;
this.root=this.root.next;
temp.next=null;
this.count--;
return;
}else{
this.foot=0;
this.root.remove(this.root,index);
}
}

//根据传入的数值删除
publicvoidremove(Tdata){
if(this.isEmpty()){
return;
}
//如果删除的正好是根节点
if(this.root.data.equals(data)){
Nodetemp=this.root;
this.root=this.root.next;
temp.next=null;
this.count--;
return;
}else{
this.root.remove(this.root,data);
}
}

//修改--根据索引修改
publicvoidreplace(intindex,TnewData){
if(this.isEmpty()){
return;
}
if(index<0||this.count<=index){
return;
}
this.foot=0;
this.root.replace(index,newData);
}

//修改--新老数据替换
publicvoidreplace(ToldData,TnewData){
if(this.isEmpty()){
return;
}
this.root.replace(oldData,newData);
}

//查询---根据索引查找
publicTget(intindex){
if(this.isEmpty()){
returnnull;
}
this.foot=0;
returnthis.root.get(index);
}

//是否包含
publicbooleancontains(Tdata){
if(this.isEmpty()){
returnfalse;
}
returnthis.root.contains(data);
}

//打印toArray
publicObject[]toArray(){
if(this.isEmpty()){
returnnull;
}
intcount=this.count;
Object[]retVal=newObject[count];
for(inti=0;i
2.验证的具体方法
booleanisPalindrome(ListNode.Nodehead){
if(head==null||head.next==null){
returntrue;
}
//
ListNode.Nodeprev=null;
//慢指针节点
ListNode.Nodeslow=head;
//快指针节点
ListNode.Nodefast=head;
//奇数的中位节点或者是偶数的下中位节点
ListNode.Nodemiddle=head;
while(fast!=null&&fast.next!=null){
//快指针每次移动2个节点
fast=fast.next.next;
//慢指针每次移动1个节点
ListNode.Nodenext=slow.next;
//前半部分的指针反向。反向后前半部分节点的next节点都是他的前一个节点
slow.next=prev;
//当前的慢指针指向前一个节点
prev=slow;
//下一个节点变为慢节点
slow=next;
//记录中位节点
middle=slow;
}
//如果fast不是null，说明此时有奇数个节点，偶数个节点时fast为null
//还没有进行if处理之前slow节点和prev节点在奇偶数的情况下分别为
//abcdcba此种情况下slow节点是d，prev节点是第1个c
//abccba此种情况下slow节点是第2个c，prev节点是第1个c
if(fast!=null){
//slow取中间节点的下一个节点，做为回文比较的起点
slow=slow.next;
}
//进行if处理结束之后，slow代表的是后半段的第一个节点，指针向后移动
//prev代表的是前半段的最后一个节点，指针向前移动
//abcdcba此种情况下slow节点是第2个c，prev节点是第1个c
//abccba此种情况下slow节点是第2个c，prev节点是第1个c
//前半部分指针恢复正常处理。将下一个节点记录下来
ListNode.Nodenext=middle;
while(slow!=null){
//进行数据比对。如果不相等则不是回文
if(slow.data!=prev.data){
returnfalse;
}
//前半部分当前节点
ListNode.Nodecurrent=prev;
//prev向前取节点
prev=prev.next;
//slow向后取节点
slow=slow.next;
//前半部分指针恢复正常处理。
current.next=next;
//本轮处理完之后，将next赋值为当前节点
next=current;
}
returntrue;
}
四.代码测试
publicstaticvoidmain(String[]args){
ListNodelistNode=newListNode();
listNode.add("a");
listNode.add("b");
listNode.add("c");
listNode.add("d");
listNode.add("e");
listNode.add("f");
listNode.add("e");
listNode.add("d");
listNode.add("c");
listNode.add("b");
listNode.add("a");
ListNodeexample=newListNode();
booleanb=example.isPalindrome(listNode.root);
System.out.println("是否是回文："+b);//true
}
五.完整代码
publicclassListNode{
/**
*根节点索引位置
*/
privateintfoot;
/**
*代表链表程度
*/
privateintcount;
/**
*标识根节点
*/
privateNoderoot;

//链接点类,内部方法实现，外部使用
privateclassNode{
//数据信息
privateTdata;
//下一个节点引用
privateNodenext;

publicNode(Tdata){
this.data=data;
}

//添加节点
privatevoidadd(Tdata){
if(this.next==null){
//如果当前节点的next为null,直接创建一个新的节点
this.next=newNode(data);
}else{
//否则进行递归调用，直到最后在某个为空的节点创建一个新节点
this.next.add(data);
}
}

//删除节点1
publicvoidremove(Nodeprevious,intindex){

if(ListNode.this.foot++==index){
//this表示当前要删除的节点
previous.next=this.next;
this.next=null;
ListNode.this.count--;
return;
}else{
//递归删除
this.next.remove(this,index);
}

}

//删除节点2
publicvoidremove(Nodeprevious,Tdata){
if(this.data.equals(data)){
previous.next=this.next;
this.next=null;
ListNode.this.count--;
return;
}else{
if(this.next!=null){
this.next.remove(this,data);
}else{
return;
}
}
}

//修改数据--新数据替换旧数据
publicvoidreplace(ToldData,TnewData){
if(this.data.equals(newData)){
this.data=newData;
}else{
//递归修改，寻找当前节点下一个节点，直到某个节点的值匹配入参
this.next.replace(oldData,newData);
}

}

//修改数据--利用索引修改
publicvoidreplace(intindex,TnewData){
if(ListNode.this.foot++==index){
//找到了某个值的索引和传入的索引相同，直接替换
this.data=newData;
}else{
this.next.replace(index,newData);
}
}

//查询
publicTget(intindex){
if(ListNode.this.foot++==index){
returnthis.data;
}else{
returnthis.next.get(index);
}
}

//链表是否包含某个节点
publicbooleancontains(Tdata){
//如果当前的这个data正好和传入的data匹配
if(this.data.equals(data)){
returntrue;
}else{
//如果当前的这个不匹配，则需要查找下一个节点
if(this.next==null){
returnfalse;
}else{
returnthis.next.contains(data);
}
}
}

}

publicListNode(){

}

//检查链表是否为空
publicbooleanisEmpty(){
if(count==0||this.root==null){
returntrue;
}else{
returnfalse;
}
}

//获取链表的长度
publicintsize(){
returnthis.count;
}

//添加
publicvoidadd(Tdata){
if(this.isEmpty()){//如果链表为空，新建一个节点
this.root=newNode(data);
}else{
this.root.add(data);
}
this.count++;
}

//删除--按照索引删除
publicvoidremove(intindex){
if(this.isEmpty()){
return;
}
if(index<0||this.count<=index){
return;
}
if(index==0){//想要删除根节点
Nodetemp=this.root;
this.root=this.root.next;
temp.next=null;
this.count--;
return;
}else{
this.foot=0;
this.root.remove(this.root,index);
}
}

//根据传入的数值删除
publicvoidremove(Tdata){
if(this.isEmpty()){
return;
}
//如果删除的正好是根节点
if(this.root.data.equals(data)){
Nodetemp=this.root;
this.root=this.root.next;
temp.next=null;
this.count--;
return;
}else{
this.root.remove(this.root,data);
}
}

//修改--根据索引修改
publicvoidreplace(intindex,TnewData){
if(this.isEmpty()){
return;
}
if(index<0||this.count<=index){
return;
}
this.foot=0;
this.root.replace(index,newData);
}

//修改--新老数据替换
publicvoidreplace(ToldData,TnewData){
if(this.isEmpty()){
return;
}
this.root.replace(oldData,newData);
}

//查询---根据索引查找
publicTget(intindex){
if(this.isEmpty()){
returnnull;
}
this.foot=0;
returnthis.root.get(index);
}

//是否包含
publicbooleancontains(Tdata){
if(this.isEmpty()){
returnfalse;
}
returnthis.root.contains(data);
}

//打印toArray
publicObject[]toArray(){
if(this.isEmpty()){
returnnull;
}
intcount=this.count;
Object[]retVal=newObject[count];
for(inti=0;ilistNode=newListNode();
listNode.add("a");
listNode.add("b");
listNode.add("c");
listNode.add("d");
listNode.add("e");
listNode.add("f");
listNode.add("e");
listNode.add("d");
listNode.add("c");
listNode.add("b");
listNode.add("a");
ListNodeexample=newListNode();
booleanb=example.isPalindrome(listNode.root);
System.out.println("是否是回文："+b);
}
}
以上就是使用JAVA实现单链表，检测字符串是否是回文串的详细内容，更多关于java封装单链表的资料请关注毛票票其它相关文章！

用JAVA实现单链表，检测字符串是否是回文串

热门推荐

随机推荐