用JAVA实现单链表,检测字符串是否是回文串
更新时间:2020年11月25日 16:01 点击:1657
一.需求
使用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); } }
以上就是使用JAVA实现单链表,检测字符串是否是回文串的详细内容,更多关于java封装单链表的资料请关注猪先飞其它相关文章!
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
- 这篇文章主要介绍了C#中截取字符串的的基本方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-03
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章介绍了C#判断字符串是否数字或字母的实例,有需要的朋友可以参考一下...2020-06-25
- 这篇文章主要介绍了PostgreSQL判断字符串是否包含目标字符串的多种方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 本文实例讲述了php字符串按照单词进行反转的方法。分享给大家供大家参考。具体分析如下:下面的php代码可以将字符串按照单词进行反转输出,实际上是现将字符串按照空格分隔到数组,然后对数组进行反转输出。...2015-03-15
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了MySQL 字符串拆分操作(含分隔符的字符串截取),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-02-22
- 这篇文章主要介绍了C#实现字符串转换成字节数组的简单实现方法,仅一行代码即可搞定,非常简单实用,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了使用list stream:任意对象List拼接字符串操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-09-09
- 这篇文章主要介绍了C# 16 进制字符串转 int的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
- JS中默认中文字符长度和其它字符长度计算方法是一样的,但某些情况下我们需要获取中文字符串的实际长度,代码如下: 复制代码 代码如下: function strLength(str) { var realLength = 0, len = str.length, charCode = -1;...2014-06-07
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02