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

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

一.需求

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

二.需求分析

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

链表存在奇偶数情况。

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

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

三.代码实现

1.单链表类封装

public class ListNode {

/**

* 根节点索引位置

*/

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);

}

}

//删除节点1http://

public void remove(Node previous, int index) {

if (ListNode.this.foothttp://++ == 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 listNode = new ListNode();

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 {

/**

* 根节点索引位置

*/

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 listNode = new ListNode();

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封装单链表的资料请关注我们其它相关文章！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。