用JAVA實現(xiàn)單鏈表，檢測字符串是否是回文串
更新時間：2020年11月25日 11:53:52 作者：未月廿三
這篇文章主要介紹了使用JAVA實現(xiàn)單鏈表，檢測字符串是否是回文串，幫助大家更好的理解和使用Java，感興趣的朋友可以了解下
一.需求
使用JAVA實現(xiàn)單鏈表，使用單鏈表檢測字符串是否是回文串
二.需求分析
回文串最重要的就是對稱，那么最重要的問題就是找到那個中心，用快指針每步走兩格，當他到達鏈表末端的時候，慢指針剛好到達中心，慢指針在遍歷過程中（快指針到達末端時）把走過的節(jié)點進行反向操作，此時從中位點分為前后兩部分，此時前半部分的指針開始往回指（取next的時候，取的是前一個節(jié)點），而慢指針繼續(xù)向前，跟前半部分的數(shù)據(jù)依次進行比對，當慢指針掃完整個鏈表，就可以判斷這是回文串，否則就提前退出，同時在前半部分往回遍歷的過程中將前半部分的指針重置成正向。
鏈表存在奇偶數(shù)情況。
奇數(shù)的時候，快指針遍歷到末端的時候，中點位即中間位置的點，此中位點下一個節(jié)點為后半部分比對開始的位置。
偶數(shù)的時候，快指針遍歷到末端的時候，中點位置此時為下中位點,此中位點就是后半部分比對開始的位置。
三.代碼實現(xiàn)
1.單鏈表類封裝
public class ListNode<T> {
/**
* 根節(jié)點索引位置
*/
private int foot;
/**
* 代表鏈表程度
*/
private int count;
/**
* 標識根節(jié)點
*/
private Node root;
//鏈接點類,內部方法實現(xiàn)，外部使用
private class Node {
//數(shù)據(jù)信息
private T data;
//下一個節(jié)點引用
private Node next;
public Node(T data) {
this.data = data;
}
//添加節(jié)點
private void add(T data) {
if (this.next == null) {
//如果當前節(jié)點的next為null,直接創(chuàng)建一個新的節(jié)點
this.next = new Node(data);
} else {
//否則進行遞歸調用，直到最后在某個為空的節(jié)點創(chuàng)建一個新節(jié)點
this.next.add(data);
}
}
//刪除節(jié)點1
public void remove(Node previous, int index) {
if (ListNode.this.foot++ == index) {
//this表示當前要刪除的節(jié)點
previous.next = this.next;
this.next = null;
ListNode.this.count--;
return;
} else {
//遞歸刪除
this.next.remove(this, index);
}
}
//刪除節(jié)點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 {
//遞歸修改，尋找當前節(jié)點下一個節(jié)點，直到某個節(jié)點的值匹配入?yún)?
this.next.replace(oldData, newData);
}
}
//修改數(shù)據(jù) -- 利用索引修改
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);
}
}
//鏈表是否包含某個節(jié)點
public boolean contains(T data) {
//如果當前的這個data正好和傳入的data匹配
if (this.data.equals(data)) {
return true;
} else {
//如果當前的這個不匹配，則需要查找下一個節(jié)點
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()) { //如果鏈表為空，新建一個節(jié)點
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é)點
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é)點
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.驗證的具體方法
boolean isPalindrome(ListNode.Node head) {
if (head == null || head.next == null) {
return true;
}
//
ListNode.Node prev = null;
//慢指針節(jié)點
ListNode.Node slow = head;
//快指針節(jié)點
ListNode.Node fast = head;
//奇數(shù)的中位節(jié)點或者是偶數(shù)的下中位節(jié)點
ListNode.Node middle = head;
while (fast != null && fast.next != null) {
//快指針每次移動2個節(jié)點
fast = fast.next.next;
//慢指針每次移動1個節(jié)點
ListNode.Node next = slow.next;
//前半部分的指針反向。反向后前半部分節(jié)點的next節(jié)點都是他的前一個節(jié)點
slow.next = prev;
//當前的慢指針指向前一個節(jié)點
prev = slow;
//下一個節(jié)點變?yōu)槁?jié)點
slow = next;
//記錄中位節(jié)點
middle = slow;
}
//如果fast不是null，說明此時有奇數(shù)個節(jié)點，偶數(shù)個節(jié)點時fast為null
//還沒有進行if處理之前slow節(jié)點和prev節(jié)點在奇偶數(shù)的情況下分別為
// a b c d c b a 此種情況下slow節(jié)點是d，prev節(jié)點是第1個c
// a b c c b a 此種情況下slow節(jié)點是第2個c，prev節(jié)點是第1個c
if (fast != null) {
//slow取中間節(jié)點的下一個節(jié)點，做為回文比較的起點
slow = slow.next;
}
//進行if處理結束之后，slow代表的是后半段的第一個節(jié)點，指針向后移動
//prev代表的是前半段的最后一個節(jié)點，指針向前移動
// a b c d c b a 此種情況下slow節(jié)點是第2個c，prev節(jié)點是第1個c
// a b c c b a 此種情況下slow節(jié)點是第2個c，prev節(jié)點是第1個c
//前半部分指針恢復正常處理。將下一個節(jié)點記錄下來
ListNode.Node next = middle;
while (slow != null) {
//進行數(shù)據(jù)比對。如果不相等則不是回文
if (slow.data != prev.data) {
return false;
}
//前半部分當前節(jié)點
ListNode.Node current = prev;
//prev向前取節(jié)點
prev = prev.next;
//slow向后取節(jié)點
slow = slow.next;
//前半部分指針恢復正常處理。
current.next = next;
//本輪處理完之后，將next賦值為當前節(jié)點
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> {
/**
* 根節(jié)點索引位置
*/
private int foot;
/**
* 代表鏈表程度
*/
private int count;
/**
* 標識根節(jié)點
*/
private Node root;
//鏈接點類,內部方法實現(xiàn)，外部使用
private class Node {
//數(shù)據(jù)信息
private T data;
//下一個節(jié)點引用
private Node next;
public Node(T data) {
this.data = data;
}
//添加節(jié)點
private void add(T data) {
if (this.next == null) {
//如果當前節(jié)點的next為null,直接創(chuàng)建一個新的節(jié)點
this.next = new Node(data);
} else {
//否則進行遞歸調用，直到最后在某個為空的節(jié)點創(chuàng)建一個新節(jié)點
this.next.add(data);
}
}
//刪除節(jié)點1
public void remove(Node previous, int index) {
if (ListNode.this.foot++ == index) {
//this表示當前要刪除的節(jié)點
previous.next = this.next;
this.next = null;
ListNode.this.count--;
return;
} else {
//遞歸刪除
this.next.remove(this, index);
}
}
//刪除節(jié)點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 {
//遞歸修改，尋找當前節(jié)點下一個節(jié)點，直到某個節(jié)點的值匹配入?yún)?
this.next.replace(oldData, newData);
}
}
//修改數(shù)據(jù) -- 利用索引修改
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);
}
}
//鏈表是否包含某個節(jié)點
public boolean contains(T data) {
//如果當前的這個data正好和傳入的data匹配
if (this.data.equals(data)) {
return true;
} else {
//如果當前的這個不匹配，則需要查找下一個節(jié)點
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()) { //如果鏈表為空，新建一個節(jié)點
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é)點
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é)點
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é)點
ListNode.Node slow = head;
//快指針節(jié)點
ListNode.Node fast = head;
//奇數(shù)的中位節(jié)點或者是偶數(shù)的下中位節(jié)點
ListNode.Node middle = head;
while (fast != null && fast.next != null) {
//快指針每次移動2個節(jié)點
fast = fast.next.next;
//慢指針每次移動1個節(jié)點
ListNode.Node next = slow.next;
//前半部分的指針反向。反向后前半部分節(jié)點的next節(jié)點都是他的前一個節(jié)點
slow.next = prev;
//當前的慢指針指向前一個節(jié)點
prev = slow;
//下一個節(jié)點變?yōu)槁?jié)點
slow = next;
//記錄中位節(jié)點
middle = slow;
}
//如果fast不是null，說明此時有奇數(shù)個節(jié)點，偶數(shù)個節(jié)點時fast為null
//還沒有進行if處理之前slow節(jié)點和prev節(jié)點在奇偶數(shù)的情況下分別為
// a b c d c b a 此種情況下slow節(jié)點是d，prev節(jié)點是第1個c
// a b c c b a 此種情況下slow節(jié)點是第2個c，prev節(jié)點是第1個c
if (fast != null) {
//slow取中間節(jié)點的下一個節(jié)點，做為回文比較的起點
slow = slow.next;
}
//進行if處理結束之后，slow代表的是后半段的第一個節(jié)點，指針向后移動
//prev代表的是前半段的最后一個節(jié)點，指針向前移動
// a b c d c b a 此種情況下slow節(jié)點是第2個c，prev節(jié)點是第1個c
// a b c c b a 此種情況下slow節(jié)點是第2個c，prev節(jié)點是第1個c
//前半部分指針恢復正常處理。將下一個節(jié)點記錄下來
ListNode.Node next = middle;
while (slow != null) {
//進行數(shù)據(jù)比對。如果不相等則不是回文
if (slow.data != prev.data) {
return false;
}
//前半部分當前節(jié)點
ListNode.Node current = prev;
//prev向前取節(jié)點
prev = prev.next;
//slow向后取節(jié)點
slow = slow.next;
//前半部分指針恢復正常處理。
current.next = next;
//本輪處理完之后，將next賦值為當前節(jié)點
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實現(xiàn)單鏈表，檢測字符串是否是回文串的詳細內容，更多關于java封裝單鏈表的資料請關注腳本之家其它相關文章！
相關文章
SpringCloud實現(xiàn)服務調用feign與熔斷hystrix和網關gateway詳細分析
這篇文章主要介紹了SpringCloud實現(xiàn)服務調用feign與熔斷hystrix和網關gateway，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習吧2023-04-04
學了java網絡，也是該做個小案例來鞏固一下了。本次案例將使用UDP和多線程模擬即時聊天，簡單練練手。2021-05-05
SpringBoot?整合Redis?數(shù)據(jù)庫的方法
Redis是一個基于內存的日志型可持久化的緩存數(shù)據(jù)庫，保存形式為key-value格式，Redis完全免費開源，它使用ANSI?C語言編寫。這篇文章主要介紹了SpringBoot?整合Redis?數(shù)據(jù)庫的方法,需要的朋友可以參考下2018-03-03
本文主要介紹了java泛型的相關知識。具有很好的參考價值。下面跟著小編一起來看下吧2017-03-03
Redisson RedLock紅鎖加鎖實現(xiàn)過程及原理
本文主要介紹了Redis中Redisson紅鎖(Redlock)使用原理，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-02-02
Springboot整合分頁插件PageHelper步驟解析
這篇文章主要介紹了Springboot整合分頁插件PageHelper步驟解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-06-06
這篇文章主要介紹了Java騷操作之CountDownLatch代碼詳解,本文通過實例圖文相結合給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-02-02
這篇文章主要介紹了Hibernate緩存機制實例代碼解析，介紹了查詢緩存，一級二級緩存等內容，分享了相關代碼示例，小編覺得還是挺不錯的，具有一定借鑒價值，需要的朋友可以參考下2018-02-02
這篇文章主要介紹了Java進程與線程的區(qū)別，進程（Process）是操作系統(tǒng)分配資源的基本單位，線程（Thread）是操作系統(tǒng)能夠進行運算調度的基本單位，下文更多兩者區(qū)別。需要的小伙伴可以參考一下2022-05-05
這篇文章主要給大家介紹了關于MyBatis中$和#的相關資料，文中通過圖文介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-10-10