如何在JAVA中使用單鏈表檢測(cè)字符串是否為回文串

如何在JAVA中使用單鏈表檢測(cè)字符串是否為回文串？針對(duì)這個(gè)問(wèn)題，這篇文章詳細(xì)介紹了相對(duì)應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問(wèn)題的小伙伴找到更簡(jiǎn)單易行的方法。

一.需求

JAVA使用單鏈表檢測(cè)字符串是否是回文串

二.需求分析

回文串最重要的就是對(duì)稱，那么最重要的問(wèn)題就是找到那個(gè)中心，用快指針每步走兩格，當(dāng)他到達(dá)鏈表末端的時(shí)候，慢指針剛好到達(dá)中心，慢指針在遍歷過(guò)程中（快指針到達(dá)末端時(shí)）把走過(guò)的節(jié)點(diǎn)進(jìn)行反向操作，此時(shí)從中位點(diǎn)分為前后兩部分，此時(shí)前半部分的指針開(kāi)始往回指（取next的時(shí)候，取的是前一個(gè)節(jié)點(diǎn)），而慢指針繼續(xù)向前，跟前半部分的數(shù)據(jù)依次進(jìn)行比對(duì)，當(dāng)慢指針掃完整個(gè)鏈表，就可以判斷這是回文串，否則就提前退出，同時(shí)在前半部分往回遍歷的過(guò)程中將前半部分的指針重置成正向。

鏈表存在奇偶數(shù)情況。

奇數(shù)的時(shí)候，快指針遍歷到末端的時(shí)候，中點(diǎn)位即中間位置的點(diǎn)，此中位點(diǎn)下一個(gè)節(jié)點(diǎn)為后半部分比對(duì)開(kāi)始的位置。
偶數(shù)的時(shí)候，快指針遍歷到末端的時(shí)候，中點(diǎn)位置此時(shí)為下中位點(diǎn),此中位點(diǎn)就是后半部分比對(duì)開(kāi)始的位置。

三.代碼實(shí)現(xiàn)

1.單鏈表類封裝

public class ListNode<T> {
 /**
  * 根節(jié)點(diǎn)索引位置
  */
 private int foot;
 /**
  * 代表鏈表程度
  */
 private int count;
 /**
  * 標(biāo)識(shí)根節(jié)點(diǎn)
  */
 private Node root;

 //鏈接點(diǎn)類,內(nèi)部方法實(shí)現(xiàn)，外部使用
 private class Node {
  //數(shù)據(jù)信息
  private T data;
  //下一個(gè)節(jié)點(diǎn)引用
  private Node next;

  public Node(T data) {
   this.data = data;
  }

  //添加節(jié)點(diǎn)
  private void add(T data) {
   if (this.next == null) {
    //如果當(dāng)前節(jié)點(diǎn)的next為null,直接創(chuàng)建一個(gè)新的節(jié)點(diǎn)
    this.next = new Node(data);
   } else {
    //否則進(jìn)行遞歸調(diào)用，直到最后在某個(gè)為空的節(jié)點(diǎn)創(chuàng)建一個(gè)新節(jié)點(diǎn)
    this.next.add(data);
   }
  }

  //刪除節(jié)點(diǎn)1
  public void remove(Node previous, int index) {

   if (ListNode.this.foot++ == index) {
    //this表示當(dāng)前要?jiǎng)h除的節(jié)點(diǎn)
    previous.next = this.next;
    this.next = null;
    ListNode.this.count--;
    return;
   } else {
    //遞歸刪除
    this.next.remove(this, index);
   }

  }

  //刪除節(jié)點(diǎn)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;
    }
   }
  }

  //修改數(shù)據(jù) -- 新數(shù)據(jù)替換舊數(shù)據(jù)
  public void replace(T oldData, T newData) {
   if (this.data.equals(newData)) {
    this.data = newData;
   } else {
    //遞歸修改，尋找當(dāng)前節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)，直到某個(gè)節(jié)點(diǎn)的值匹配入?yún)?
    this.next.replace(oldData, newData);
   }

  }

  //修改數(shù)據(jù) -- 利用索引修改
  public void replace(int index, T newData) {
   if (ListNode.this.foot++ == index) {
    //找到了某個(gè)值的索引和傳入的索引相同，直接替換
    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);
   }
  }

  //鏈表是否包含某個(gè)節(jié)點(diǎn)
  public boolean contains(T data) {
   //如果當(dāng)前的這個(gè)data正好和傳入的data匹配
   if (this.data.equals(data)) {
    return true;
   } else {
    //如果當(dāng)前的這個(gè)不匹配，則需要查找下一個(gè)節(jié)點(diǎn)
    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;
  }
 }

 //獲取鏈表的長(zhǎng)度
 public int size() {
  return this.count;
 }

 //添加
 public void add(T data) {
  if (this.isEmpty()) { //如果鏈表為空，新建一個(gè)節(jié)點(diǎn)
   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) { //想要?jiǎng)h除根節(jié)點(diǎn)
   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);
  }
 }

 //根據(jù)傳入的數(shù)值刪除
 public void remove(T data) {
  if (this.isEmpty()) {
   return;
  }
  //如果刪除的正好是根節(jié)點(diǎn)
  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);
  }
 }

 //修改 -- 根據(jù)索引修改
 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);
 }

 //修改 -- 新老數(shù)據(jù)替換
 public void replace(T oldData, T newData) {
  if (this.isEmpty()) {
   return;
  }
  this.root.replace(oldData, newData);
 }

 //查詢 --- 根據(jù)索引查找
 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.驗(yàn)證的具體方法

boolean isPalindrome(ListNode.Node head) {
 if (head == null || head.next == null) {
  return true;
 }
 //
 ListNode.Node prev = null;
 //慢指針節(jié)點(diǎn)
 ListNode.Node slow = head;
 //快指針節(jié)點(diǎn)
 ListNode.Node fast = head;
 //奇數(shù)的中位節(jié)點(diǎn)或者是偶數(shù)的下中位節(jié)點(diǎn)
 ListNode.Node middle = head;
 while (fast != null && fast.next != null) {
  //快指針每次移動(dòng)2個(gè)節(jié)點(diǎn)
  fast = fast.next.next;
  //慢指針每次移動(dòng)1個(gè)節(jié)點(diǎn)
  ListNode.Node next = slow.next;
  //前半部分的指針?lè)聪颉７聪蚝笄鞍氩糠止?jié)點(diǎn)的next節(jié)點(diǎn)都是他的前一個(gè)節(jié)點(diǎn)
  slow.next = prev;
  //當(dāng)前的慢指針指向前一個(gè)節(jié)點(diǎn)
  prev = slow;
  //下一個(gè)節(jié)點(diǎn)變?yōu)槁?jié)點(diǎn)
  slow = next;
  //記錄中位節(jié)點(diǎn)
  middle = slow;
 }
 //如果fast不是null，說(shuō)明此時(shí)有奇數(shù)個(gè)節(jié)點(diǎn)，偶數(shù)個(gè)節(jié)點(diǎn)時(shí)fast為null
 //還沒(méi)有進(jìn)行if處理之前slow節(jié)點(diǎn)和prev節(jié)點(diǎn)在奇偶數(shù)的情況下分別為
 // a b c d c b a 此種情況下slow節(jié)點(diǎn)是d，prev節(jié)點(diǎn)是第1個(gè)c
 // a b c c b a 此種情況下slow節(jié)點(diǎn)是第2個(gè)c，prev節(jié)點(diǎn)是第1個(gè)c
 if (fast != null) {
  //slow取中間節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，做為回文比較的起點(diǎn)
  slow = slow.next;
 }
 //進(jìn)行if處理結(jié)束之后，slow代表的是后半段的第一個(gè)節(jié)點(diǎn)，指針向后移動(dòng)
 //prev代表的是前半段的最后一個(gè)節(jié)點(diǎn)，指針向前移動(dòng)
 // a b c d c b a 此種情況下slow節(jié)點(diǎn)是第2個(gè)c，prev節(jié)點(diǎn)是第1個(gè)c
 // a b c c b a 此種情況下slow節(jié)點(diǎn)是第2個(gè)c，prev節(jié)點(diǎn)是第1個(gè)c
 //前半部分指針恢復(fù)正常處理。將下一個(gè)節(jié)點(diǎn)記錄下來(lái)
 ListNode.Node next = middle;
 while (slow != null) {
  //進(jìn)行數(shù)據(jù)比對(duì)。如果不相等則不是回文
  if (slow.data != prev.data) {
  return false;
  }
  //前半部分當(dāng)前節(jié)點(diǎn)
  ListNode.Node current = prev;
  //prev向前取節(jié)點(diǎn)
  prev = prev.next;
  //slow向后取節(jié)點(diǎn)
  slow = slow.next;
  //前半部分指針恢復(fù)正常處理。
  current.next = next;
  //本輪處理完之后，將next賦值為當(dāng)前節(jié)點(diǎn)
  next = current;
 }
 return true;
}

四.代碼測(cè)試

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> {
 /**
  * 根節(jié)點(diǎn)索引位置
  */
 private int foot;
 /**
  * 代表鏈表程度
  */
 private int count;
 /**
  * 標(biāo)識(shí)根節(jié)點(diǎn)
  */
 private Node root;

 //鏈接點(diǎn)類,內(nèi)部方法實(shí)現(xiàn)，外部使用
 private class Node {
  //數(shù)據(jù)信息
  private T data;
  //下一個(gè)節(jié)點(diǎn)引用
  private Node next;

  public Node(T data) {
   this.data = data;
  }

  //添加節(jié)點(diǎn)
  private void add(T data) {
   if (this.next == null) {
    //如果當(dāng)前節(jié)點(diǎn)的next為null,直接創(chuàng)建一個(gè)新的節(jié)點(diǎn)
    this.next = new Node(data);
   } else {
    //否則進(jìn)行遞歸調(diào)用，直到最后在某個(gè)為空的節(jié)點(diǎn)創(chuàng)建一個(gè)新節(jié)點(diǎn)
    this.next.add(data);
   }
  }

  //刪除節(jié)點(diǎn)1
  public void remove(Node previous, int index) {

   if (ListNode.this.foot++ == index) {
    //this表示當(dāng)前要?jiǎng)h除的節(jié)點(diǎn)
    previous.next = this.next;
    this.next = null;
    ListNode.this.count--;
    return;
   } else {
    //遞歸刪除
    this.next.remove(this, index);
   }

  }

  //刪除節(jié)點(diǎn)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;
    }
   }
  }

  //修改數(shù)據(jù) -- 新數(shù)據(jù)替換舊數(shù)據(jù)
  public void replace(T oldData, T newData) {
   if (this.data.equals(newData)) {
    this.data = newData;
   } else {
    //遞歸修改，尋找當(dāng)前節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)，直到某個(gè)節(jié)點(diǎn)的值匹配入?yún)?
    this.next.replace(oldData, newData);
   }

  }

  //修改數(shù)據(jù) -- 利用索引修改
  public void replace(int index, T newData) {
   if (ListNode.this.foot++ == index) {
    //找到了某個(gè)值的索引和傳入的索引相同，直接替換
    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);
   }
  }

  //鏈表是否包含某個(gè)節(jié)點(diǎn)
  public boolean contains(T data) {
   //如果當(dāng)前的這個(gè)data正好和傳入的data匹配
   if (this.data.equals(data)) {
    return true;
   } else {
    //如果當(dāng)前的這個(gè)不匹配，則需要查找下一個(gè)節(jié)點(diǎn)
    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;
  }
 }

 //獲取鏈表的長(zhǎng)度
 public int size() {
  return this.count;
 }

 //添加
 public void add(T data) {
  if (this.isEmpty()) { //如果鏈表為空，新建一個(gè)節(jié)點(diǎn)
   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) { //想要?jiǎng)h除根節(jié)點(diǎn)
   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);
  }
 }

 //根據(jù)傳入的數(shù)值刪除
 public void remove(T data) {
  if (this.isEmpty()) {
   return;
  }
  //如果刪除的正好是根節(jié)點(diǎn)
  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);
  }
 }

 //修改 -- 根據(jù)索引修改
 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);
 }

 //修改 -- 新老數(shù)據(jù)替換
 public void replace(T oldData, T newData) {
  if (this.isEmpty()) {
   return;
  }
  this.root.replace(oldData, newData);
 }

 //查詢 --- 根據(jù)索引查找
 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;
  //慢指針節(jié)點(diǎn)
  ListNode.Node slow = head;
  //快指針節(jié)點(diǎn)
  ListNode.Node fast = head;
  //奇數(shù)的中位節(jié)點(diǎn)或者是偶數(shù)的下中位節(jié)點(diǎn)
  ListNode.Node middle = head;
  while (fast != null && fast.next != null) {
   //快指針每次移動(dòng)2個(gè)節(jié)點(diǎn)
   fast = fast.next.next;
   //慢指針每次移動(dòng)1個(gè)節(jié)點(diǎn)
   ListNode.Node next = slow.next;
   //前半部分的指針?lè)聪?。反向后前半部分?jié)點(diǎn)的next節(jié)點(diǎn)都是他的前一個(gè)節(jié)點(diǎn)
   slow.next = prev;
   //當(dāng)前的慢指針指向前一個(gè)節(jié)點(diǎn)
   prev = slow;
   //下一個(gè)節(jié)點(diǎn)變?yōu)槁?jié)點(diǎn)
   slow = next;
   //記錄中位節(jié)點(diǎn)
   middle = slow;
  }
  //如果fast不是null，說(shuō)明此時(shí)有奇數(shù)個(gè)節(jié)點(diǎn)，偶數(shù)個(gè)節(jié)點(diǎn)時(shí)fast為null
  //還沒(méi)有進(jìn)行if處理之前slow節(jié)點(diǎn)和prev節(jié)點(diǎn)在奇偶數(shù)的情況下分別為
  // a b c d c b a 此種情況下slow節(jié)點(diǎn)是d，prev節(jié)點(diǎn)是第1個(gè)c
  // a b c c b a 此種情況下slow節(jié)點(diǎn)是第2個(gè)c，prev節(jié)點(diǎn)是第1個(gè)c
  if (fast != null) {
   //slow取中間節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，做為回文比較的起點(diǎn)
   slow = slow.next;
  }
  //進(jìn)行if處理結(jié)束之后，slow代表的是后半段的第一個(gè)節(jié)點(diǎn)，指針向后移動(dòng)
  //prev代表的是前半段的最后一個(gè)節(jié)點(diǎn)，指針向前移動(dòng)
  // a b c d c b a 此種情況下slow節(jié)點(diǎn)是第2個(gè)c，prev節(jié)點(diǎn)是第1個(gè)c
  // a b c c b a 此種情況下slow節(jié)點(diǎn)是第2個(gè)c，prev節(jié)點(diǎn)是第1個(gè)c
  //前半部分指針恢復(fù)正常處理。將下一個(gè)節(jié)點(diǎn)記錄下來(lái)
  ListNode.Node next = middle;
  while (slow != null) {
   //進(jìn)行數(shù)據(jù)比對(duì)。如果不相等則不是回文
   if (slow.data != prev.data) {
    return false;
   }
   //前半部分當(dāng)前節(jié)點(diǎn)
   ListNode.Node current = prev;
   //prev向前取節(jié)點(diǎn)
   prev = prev.next;
   //slow向后取節(jié)點(diǎn)
   slow = slow.next;
   //前半部分指針恢復(fù)正常處理。
   current.next = next;
   //本輪處理完之后，將next賦值為當(dāng)前節(jié)點(diǎn)
   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);
 }
}

關(guān)于如何在JAVA中使用單鏈表檢測(cè)字符串是否為回文串問(wèn)題的解答就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，如果你還有很多疑惑沒(méi)有解開(kāi)，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識(shí)。