用JAVA實(shí)現(xiàn)單鏈表，檢測(cè)字符串是否是回文串
更新時(shí)間：2020年11月25日 11:53:52 作者：未月廿三
這篇文章主要介紹了使用JAVA實(shí)現(xiàn)單鏈表，檢測(cè)字符串是否是回文串，幫助大家更好的理解和使用Java，感興趣的朋友可以了解下
一.需求
使用JAVA實(shí)現(xiàn)單鏈表，使用單鏈表檢測(cè)字符串是否是回文串
二.需求分析
回文串最重要的就是對(duì)稱(chēng)，那么最重要的問(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.單鏈表類(lèi)封裝
public class ListNode<T> {
/**
* 根節(jié)點(diǎn)索引位置
*/
private int foot;
/**
* 代表鏈表程度
*/
private int count;
/**
* 標(biāo)識(shí)根節(jié)點(diǎn)
*/
private Node root;
//鏈接點(diǎn)類(lèi),內(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);
}
}
//查詢(xún)
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);
}
//查詢(xún) --- 根據(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)類(lèi),內(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);
}
}
//查詢(xún)
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);
}
//查詢(xún) --- 根據(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);
}
}
以上就是使用JAVA實(shí)現(xiàn)單鏈表，檢測(cè)字符串是否是回文串的詳細(xì)內(nèi)容，更多關(guān)于java封裝單鏈表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
Springboot之如何統(tǒng)計(jì)代碼執(zhí)行耗時(shí)時(shí)間
這篇文章主要介紹了Springboot之如何統(tǒng)計(jì)代碼執(zhí)行耗時(shí)時(shí)間問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-03-03
這篇文章主要介紹了使用BigDecimal除法后保留兩位小數(shù)方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-06-06
一次Spring無(wú)法啟動(dòng)的問(wèn)題排查實(shí)戰(zhàn)之字節(jié)碼篇
最近學(xué)習(xí)了spring相關(guān)知識(shí),公司項(xiàng)目也用到了spring,下面這篇文章主要給大家介紹了一次Spring無(wú)法啟動(dòng)的問(wèn)題排查實(shí)戰(zhàn)之字節(jié)碼篇的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-04-04
Java程序圖形用戶(hù)界面設(shè)計(jì)之按鈕與布局
圖形界面（簡(jiǎn)稱(chēng)GUI）是指采用圖形方式顯示的計(jì)算機(jī)操作用戶(hù)界面。與早期計(jì)算機(jī)使用的命令行界面相比，圖形界面對(duì)于用戶(hù)來(lái)說(shuō)在視覺(jué)上更易于接受，本篇精講Java語(yǔ)言中關(guān)于圖形用戶(hù)界面的按鈕和布局部分2022-02-02
基于Java實(shí)現(xiàn)Socket編程入門(mén)
Java最初是作為網(wǎng)絡(luò)編程語(yǔ)言出現(xiàn)的，使得客戶(hù)端和服務(wù)器的溝通變成了現(xiàn)實(shí)，而在網(wǎng)絡(luò)編程中，使用最多的就是Socket，本文就來(lái)介紹一下基于Java實(shí)現(xiàn)Socket編程入門(mén)，感興趣的可以來(lái)了解一下2022-03-03
這篇文章主要介紹了Java實(shí)現(xiàn)多文件壓縮打包的方法,結(jié)合實(shí)例形式分析了java實(shí)現(xiàn)zip文件壓縮與解壓縮相關(guān)操作技巧,需要的朋友可以參考下2017-06-06
SpringBoot @ControllerAdvice 攔截異常并統(tǒng)一處理
這篇文章主要介紹了SpringBoot @ControllerAdvice 攔截異常并統(tǒng)一處理，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09
當(dāng)jvm進(jìn)程退出的時(shí)候,或者受到了系統(tǒng)的中斷信號(hào),hook線(xiàn)程就會(huì)啟動(dòng),一個(gè)線(xiàn)程可以注入多個(gè)鉤,下面這篇文章主要給大家介紹了關(guān)于JVM鉤子函數(shù)使用的相關(guān)資料,需要的朋友可以參考下2021-08-08
這篇文章主要為大家詳細(xì)介紹了23種設(shè)計(jì)模式之java代理模式，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-11-11
IDEA?2021.3?使用及idea2021.3.1激活使用方法
IDEA?全稱(chēng)?IntelliJ?IDEA，是java語(yǔ)言開(kāi)發(fā)的集成環(huán)境，IntelliJ在業(yè)界被公認(rèn)為最好的java開(kāi)發(fā)工具之一，今天通過(guò)本文給大家介紹idea2021.3.1激活及使用教程，感興趣的朋友一起看看吧2022-01-01