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

以上就是使用JAVA实现单链表，检测字符串是否是回文串的详细内容，更多关于java封装单链表的资料请关注我们其它相关文章！