用JAVA实现单链表，检测字符串是否是回文串
作者：未月廿三 发布时间：2021-07-20 07:07:45
标签：java,单链表,字符串,回文
一.需求
使用JAVA实现单链表，使用单链表检测字符串是否是回文串
二.需求分析
回文串最重要的就是对称，那么最重要的问题就是找到那个中心，用快指针每步走两格，当他到达链表末端的时候，慢指针刚好到达中心，慢指针在遍历过程中（快指针到达末端时）把走过的节点进行反向操作，此时从中位点分为前后两部分，此时前半部分的指针开始往回指（取next的时候，取的是前一个节点），而慢指针继续向前，跟前半部分的数据依次进行比对，当慢指针扫完整个链表，就可以判断这是回文串，否则就提前退出，同时在前半部分往回遍历的过程中将前半部分的指针重置成正向。
链表存在奇偶数情况。
奇数的时候，快指针遍历到末端的时候，中点位即中间位置的点，此中位点下一个节点为后半部分比对开始的位置。
偶数的时候，快指针遍历到末端的时候，中点位置此时为下中位点,此中位点就是后半部分比对开始的位置。
三.代码实现
1.单链表类封装
public class ListNode<T> {
/**
* 根节点索引位置
*/
private int foot;
/**
* 代表链表程度
*/
private int count;
/**
* 标识根节点
*/
private Node root;
//链接点类,内部方法实现，外部使用
private class Node {
//数据信息
private T data;
//下一个节点引用
private Node next;
public Node(T data) {
this.data = data;
}
//添加节点
private void add(T data) {
if (this.next == null) {
//如果当前节点的next为null,直接创建一个新的节点
this.next = new Node(data);
} else {
//否则进行递归调用，直到最后在某个为空的节点创建一个新节点
this.next.add(data);
}
}
//删除节点1
public void remove(Node previous, int index) {
if (ListNode.this.foot++ == index) {
//this表示当前要删除的节点
previous.next = this.next;
this.next = null;
ListNode.this.count--;
return;
} else {
//递归删除
this.next.remove(this, index);
}
}
//删除节点2
public void remove(Node previous, T data) {
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;
}
}
}
//修改数据 -- 新数据替换旧数据
public void replace(T oldData, T newData) {
if (this.data.equals(newData)) {
this.data = newData;
} else {
//递归修改，寻找当前节点下一个节点，直到某个节点的值匹配入参
this.next.replace(oldData, newData);
}
}
//修改数据 -- 利用索引修改
public void replace(int index, T newData) {
if (ListNode.this.foot++ == index) {
//找到了某个值的索引和传入的索引相同，直接替换
this.data = newData;
} else {
this.next.replace(index, newData);
}
}
//查询
public T get(int index) {
if (ListNode.this.foot++ == index) {
return this.data;
} else {
return this.next.get(index);
}
}
//链表是否包含某个节点
public boolean contains(T data) {
//如果当前的这个data正好和传入的data匹配
if (this.data.equals(data)) {
return true;
} else {
//如果当前的这个不匹配，则需要查找下一个节点
if (this.next == null) {
return false;
} else {
return this.next.contains(data);
}
}
}
}
public ListNode() {
}
//检查链表是否为空
public boolean isEmpty() {
if (count == 0 || this.root == null) {
return true;
} else {
return false;
}
}
//获取链表的长度
public int size() {
return this.count;
}
//添加
public void add(T data) {
if (this.isEmpty()) { //如果链表为空，新建一个节点
this.root = new Node(data);
} else {
this.root.add(data);
}
this.count++;
}
//删除 -- 按照索引删除
public void remove(int index) {
if (this.isEmpty()) {
return;
}
if (index < 0 || this.count <= index) {
return;
}
if (index == 0) { //想要删除根节点
Node temp = this.root;
this.root = this.root.next;
temp.next = null;
this.count--;
return;
} else {
this.foot = 0;
this.root.remove(this.root, index);
}
}
//根据传入的数值删除
public void remove(T data) {
if (this.isEmpty()) {
return;
}
//如果删除的正好是根节点
if (this.root.data.equals(data)) {
Node temp = this.root;
this.root = this.root.next;
temp.next = null;
this.count--;
return;
} else {
this.root.remove(this.root, data);
}
}
//修改 -- 根据索引修改
public void replace(int index, T newData) {
if (this.isEmpty()) {
return;
}
if (index < 0 || this.count <= index) {
return;
}
this.foot = 0;
this.root.replace(index, newData);
}
//修改 -- 新老数据替换
public void replace(T oldData, T newData) {
if (this.isEmpty()) {
return;
}
this.root.replace(oldData, newData);
}
//查询 --- 根据索引查找
public T get(int index) {
if (this.isEmpty()) {
return null;
}
this.foot = 0;
return this.root.get(index);
}
//是否包含
public boolean contains(T data) {
if (this.isEmpty()) {
return false;
}
return this.root.contains(data);
}
//打印 toArray
public Object[] toArray() {
if (this.isEmpty()) {
return null;
}
int count = this.count;
Object[] retVal = new Object[count];
for (int i = 0; i < count; i++) {
retVal[i] = this.get(i);
}
return retVal;
}
}
2.验证的具体方法
boolean isPalindrome(ListNode.Node head) {
if (head == null || head.next == null) {
return true;
}
//
ListNode.Node prev = null;
//慢指针节点
ListNode.Node slow = head;
//快指针节点
ListNode.Node fast = head;
//奇数的中位节点或者是偶数的下中位节点
ListNode.Node middle = head;
while (fast != null && fast.next != null) {
//快指针每次移动2个节点
fast = fast.next.next;
//慢指针每次移动1个节点
ListNode.Node next = slow.next;
//前半部分的指针反向。反向后前半部分节点的next节点都是他的前一个节点
slow.next = prev;
//当前的慢指针指向前一个节点
prev = slow;
//下一个节点变为慢节点
slow = next;
//记录中位节点
middle = slow;
}
//如果fast不是null，说明此时有奇数个节点，偶数个节点时fast为null
//还没有进行if处理之前slow节点和prev节点在奇偶数的情况下分别为
// a b c d c b a 此种情况下slow节点是d，prev节点是第1个c
// a b c c b a 此种情况下slow节点是第2个c，prev节点是第1个c
if (fast != null) {
//slow取中间节点的下一个节点，做为回文比较的起点
slow = slow.next;
}
//进行if处理结束之后，slow代表的是后半段的第一个节点，指针向后移动
//prev代表的是前半段的最后一个节点，指针向前移动
// a b c d c b a 此种情况下slow节点是第2个c，prev节点是第1个c
// a b c c b a 此种情况下slow节点是第2个c，prev节点是第1个c
//前半部分指针恢复正常处理。将下一个节点记录下来
ListNode.Node next = middle;
while (slow != null) {
//进行数据比对。如果不相等则不是回文
if (slow.data != prev.data) {
return false;
}
//前半部分当前节点
ListNode.Node current = prev;
//prev向前取节点
prev = prev.next;
//slow向后取节点
slow = slow.next;
//前半部分指针恢复正常处理。
current.next = next;
//本轮处理完之后，将next赋值为当前节点
next = current;
}
return true;
}
四.代码测试
public static void main(String[] args) {
ListNode<String> listNode = new ListNode<String>();
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");
ListNode example = new ListNode();
boolean b = example.isPalindrome(listNode.root);
System.out.println("是否是回文：" + b);//true
}
五.完整代码
public class ListNode<T> {
/**
* 根节点索引位置
*/
private int foot;
/**
* 代表链表程度
*/
private int count;
/**
* 标识根节点
*/
private Node root;
//链接点类,内部方法实现，外部使用
private class Node {
//数据信息
private T data;
//下一个节点引用
private Node next;
public Node(T data) {
this.data = data;
}
//添加节点
private void add(T data) {
if (this.next == null) {
//如果当前节点的next为null,直接创建一个新的节点
this.next = new Node(data);
} else {
//否则进行递归调用，直到最后在某个为空的节点创建一个新节点
this.next.add(data);
}
}
//删除节点1
public void remove(Node previous, int index) {
if (ListNode.this.foot++ == index) {
//this表示当前要删除的节点
previous.next = this.next;
this.next = null;
ListNode.this.count--;
return;
} else {
//递归删除
this.next.remove(this, index);
}
}
//删除节点2
public void remove(Node previous, T data) {
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;
}
}
}
//修改数据 -- 新数据替换旧数据
public void replace(T oldData, T newData) {
if (this.data.equals(newData)) {
this.data = newData;
} else {
//递归修改，寻找当前节点下一个节点，直到某个节点的值匹配入参
this.next.replace(oldData, newData);
}
}
//修改数据 -- 利用索引修改
public void replace(int index, T newData) {
if (ListNode.this.foot++ == index) {
//找到了某个值的索引和传入的索引相同，直接替换
this.data = newData;
} else {
this.next.replace(index, newData);
}
}
//查询
public T get(int index) {
if (ListNode.this.foot++ == index) {
return this.data;
} else {
return this.next.get(index);
}
}
//链表是否包含某个节点
public boolean contains(T data) {
//如果当前的这个data正好和传入的data匹配
if (this.data.equals(data)) {
return true;
} else {
//如果当前的这个不匹配，则需要查找下一个节点
if (this.next == null) {
return false;
} else {
return this.next.contains(data);
}
}
}
}
public ListNode() {
}
//检查链表是否为空
public boolean isEmpty() {
if (count == 0 || this.root == null) {
return true;
} else {
return false;
}
}
//获取链表的长度
public int size() {
return this.count;
}
//添加
public void add(T data) {
if (this.isEmpty()) { //如果链表为空，新建一个节点
this.root = new Node(data);
} else {
this.root.add(data);
}
this.count++;
}
//删除 -- 按照索引删除
public void remove(int index) {
if (this.isEmpty()) {
return;
}
if (index < 0 || this.count <= index) {
return;
}
if (index == 0) { //想要删除根节点
Node temp = this.root;
this.root = this.root.next;
temp.next = null;
this.count--;
return;
} else {
this.foot = 0;
this.root.remove(this.root, index);
}
}
//根据传入的数值删除
public void remove(T data) {
if (this.isEmpty()) {
return;
}
//如果删除的正好是根节点
if (this.root.data.equals(data)) {
Node temp = this.root;
this.root = this.root.next;
temp.next = null;
this.count--;
return;
} else {
this.root.remove(this.root, data);
}
}
//修改 -- 根据索引修改
public void replace(int index, T newData) {
if (this.isEmpty()) {
return;
}
if (index < 0 || this.count <= index) {
return;
}
this.foot = 0;
this.root.replace(index, newData);
}
//修改 -- 新老数据替换
public void replace(T oldData, T newData) {
if (this.isEmpty()) {
return;
}
this.root.replace(oldData, newData);
}
//查询 --- 根据索引查找
public T get(int index) {
if (this.isEmpty()) {
return null;
}
this.foot = 0;
return this.root.get(index);
}
//是否包含
public boolean contains(T data) {
if (this.isEmpty()) {
return false;
}
return this.root.contains(data);
}
//打印 toArray
public Object[] toArray() {
if (this.isEmpty()) {
return null;
}
int count = this.count;
Object[] retVal = new Object[count];
for (int i = 0; i < count; i++) {
retVal[i] = this.get(i);
}
return retVal;
}
boolean isPalindrome(ListNode.Node head) {
if (head == null || head.next == null) {
return true;
}
//
ListNode.Node prev = null;
//慢指针节点
ListNode.Node slow = head;
//快指针节点
ListNode.Node fast = head;
//奇数的中位节点或者是偶数的下中位节点
ListNode.Node middle = head;
while (fast != null && fast.next != null) {
//快指针每次移动2个节点
fast = fast.next.next;
//慢指针每次移动1个节点
ListNode.Node next = slow.next;
//前半部分的指针反向。反向后前半部分节点的next节点都是他的前一个节点
slow.next = prev;
//当前的慢指针指向前一个节点
prev = slow;
//下一个节点变为慢节点
slow = next;
//记录中位节点
middle = slow;
}
//如果fast不是null，说明此时有奇数个节点，偶数个节点时fast为null
//还没有进行if处理之前slow节点和prev节点在奇偶数的情况下分别为
// a b c d c b a 此种情况下slow节点是d，prev节点是第1个c
// a b c c b a 此种情况下slow节点是第2个c，prev节点是第1个c
if (fast != null) {
//slow取中间节点的下一个节点，做为回文比较的起点
slow = slow.next;
}
//进行if处理结束之后，slow代表的是后半段的第一个节点，指针向后移动
//prev代表的是前半段的最后一个节点，指针向前移动
// a b c d c b a 此种情况下slow节点是第2个c，prev节点是第1个c
// a b c c b a 此种情况下slow节点是第2个c，prev节点是第1个c
//前半部分指针恢复正常处理。将下一个节点记录下来
ListNode.Node next = middle;
while (slow != null) {
//进行数据比对。如果不相等则不是回文
if (slow.data != prev.data) {
return false;
}
//前半部分当前节点
ListNode.Node current = prev;
//prev向前取节点
prev = prev.next;
//slow向后取节点
slow = slow.next;
//前半部分指针恢复正常处理。
current.next = next;
//本轮处理完之后，将next赋值为当前节点
next = current;
}
return true;
}
public static void main(String[] args) {
ListNode<String> listNode = new ListNode<String>();
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");
ListNode example = new ListNode();
boolean b = example.isPalindrome(listNode.root);
System.out.println("是否是回文：" + b);
}
}
来源：https://www.cnblogs.com/eternityz/p/13748152.html
0
投稿猜你喜欢
在C++中，当你去创建一个类的时候，即便这个类是空类，也会自动生成下面6个默认成员函数，在本篇博客中，我将逐一分析下面6个默认成员函数。构造- 本文实例为大家分享了Android自定义带圆点的半圆形进度条，供大家参考，具体内容如下仅限用于半圆形,如须要带圆点的圆形进度条,圆点会出现错
- 前言终于来到了Maven的插件开发，其实Maven的插件并没有想象的那么难，刚开始讲Maven基础的时候就演示了一下JDK是如何打包的，Ma
- jar包打包实现jar包打包可以使用jar指令实现打包，在命令行中输入jar可以查看jar指令的内容 从最后显示的两个示例看出存在两种打包的
- 多亏了<include />标签，在Android里，很容易就能做到共享和重用UI组件。在Android开发中，很容易就能创建出
- 如今，互联网项目对于安全的要求越来越严格，这就是对后端开发提出了更多的要求，目前比较成熟的几种大家比较熟悉的模式，像RBAC 基于角色权限的
- 介绍使用mybatis时可以使用二级缓存提高查询速度，进而改善用户体验。使用redis做mybatis的二级缓存可是内存可控<如将单独
- 引言Android studio 是2020 年的版本，有点老，昨天突发想法，升级到了 Android Studio Electric Ee
- Transactional事务的使用及注意Transactional的事务使用，主要引用两个包中的Bean，一个是jpa的javax.tra
- analyzer的使用规则查询只能查找倒排索引表中真实存在的项， 所以保证文档在索引时与查询字符串在搜索时应用相同的分析过程非常重要，这样查
- 废话不多说,先看效果，如果大家感觉不错，请参考实现代码这个功能我是用Fragmentdialog里面做的,也遇到不少坑第一,就是设置背景的d
- 本文实例为大家分享了Unity实现简单虚拟摇杆的具体代码，供大家参考，具体内容如下需求：点击创建一个虚拟摇杆底盘，鼠标拖拽时候上方摇杆会跟随
- 如何给请求添加header背景：在集成了swagger的项目中，调用后台接口往往会经过一些自定义的 * ，而 * 加了token限制的话，直
- 工欲善其事，必先利其器，对于想要深入学习Android源码，必须先掌握Android编译命令.一、引言关于Android Build系统，这
- 简介散列函数（英语：Hash function）又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数
- 本文实例讲述了Java基于Runtime调用外部程序出现阻塞的解决方法， 是一个很实用的技巧。分享给大家供大家参考。具体分析如下：有时候在j
- 前言：发现用Winform做一个圆角按钮遇到麻烦，主要是锯齿问题，后面想了想办法解决问题了。主要方法是按钮的区域通过Region指定，但按钮
- 本文实例为大家分享了Struts2框架拦截 器实例的示例代码，供大家参考，具体内容如下在看拦截 器的小例子的前我们先来看看sturts2的原
- 有些人可能对线程池比较陌生，并且更不熟悉线程池的工作原理。所以他们在使用线程的时候，多数情况下都是new Thread来实现多线程。但是，往
- //Main:using System;using System.Collections.Generic;using System.Linq
