欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-16 21:38:59
一.需求使用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封装单链表的资料请关注其它相关文章!