用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封裝單鏈表的資料請關注好吧啦網其它相關文章！
網公網安備