座右銘：代碼虐我千百遍，我待代碼如初戀！！！
給定一個單鏈表的頭節點head，請判斷該鏈表是否為回文結構，
- 堆疊方法特別簡單（筆試用)
- 改原鏈表的方法就需要注意邊界了（面試用）
第一種方法：用一個堆疊來輔助實作，將鏈表從頭結點開始依次壓入堆疊中，之后再從堆疊頂依次彈出并與原鏈表一個一個進行比較，，如果相比較的程序全部相同，說明是回文結構，如果有一個比對不上就不是回文結構，因為堆疊的特征是先進后出的，所以彈出的程序就是逆序的程序，這個方法比較簡單，缺點就是費點空間，需要O(N)的空間復雜度
第二中方法：第一種基礎上改進一下，同樣需要一個堆疊來輔助實作，但是只需要用到堆疊的一半空間，所以空間復雜度為O(N/2)，額外申請兩個變數，一個快指標和慢指標，讓慢指標指向鏈表右半部分的第一個結點，然后將右半部分壓入堆疊中，再從堆疊中彈出和左半部分一一比較
第三中方法：不用申請堆疊，只需要O(1)的空間復雜度，申請一個快指標和慢指標，鏈表結點個數為奇數的時候慢指標來到中點位置，；偶數個的時候，慢指標來到上中點位置，然后將右半部分鏈表反轉，慢指標指向的結點指向空，此時再讓慢指標和快指標分別從最右邊和最左邊開始一一進行比較，最后回傳結果之前一定要將右半部分鏈表反轉回來！！！此方法難點在于難摳邊界，但是是最優解，適合面試的時候和面試官聊聊哈哈哈~~~///(v)\\\~~~
package com.harrison.class06;
import java.util.Stack;
public class Code02_IsPalindromeList {
public static class Node {
public int value;
public Node next;
public Node(int v) {
value = v;
}
}
// need n extra space
public static boolean isPalindrome1(Node head) {
Stack<Node> stack = new Stack<Node>();
Node cur = head;
// 將鏈表從頭結點開始依次壓入堆疊中
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
// 從堆疊頂依次彈出和鏈表開始比較
while (head != null) {
if (head.value != stack.pop().value) {
return false;
}
head = head.next;
}
return true;
}
// need n/2 extra space
public static boolean isPalindrome2(Node head) {
if (head == null || head.next == null) {
return true;
}
Node right = head.next;// 慢指標
Node cur = head;// 快指標
while (cur.next != null && cur.next.next != null) {
right = right.next;
cur = cur.next.next;
}
// right來到中點位置
Stack<Node> stack = new Stack<>();
// 鏈表的右半部分依次壓入堆疊中
while (right != null) {
stack.push(right);
right = right.next;
}
// 從堆疊中依次彈出 和鏈表左部分依次比較
while (!stack.isEmpty()) {
if (head.value != stack.pop().value) {
return false;
}
head = head.next;
}
return true;
}
// need O(1) extra space
public static boolean isPalindrome3(Node head) {
if (head == null || head.next == null) {
return true;
}
Node n1 = head;// 慢指標 n1 -> mid
Node n2 = head;// 快指標 n2 -> end
while (n2.next != null && n2.next.next != null) {
n1 = n1.next;
n2 = n2.next.next;
}
// 慢指標來到中點或者上中點位置 快指標來到終點
n2 = n1.next;// n2 來到右部分第一個結點
n1.next = null;// n1.next -> null
Node n3 = null;
// 右部分反轉
while (n2 != null) {
n3 = n2.next;// n3 -> save next node
n2.next = n1;// next of right node convert
n1 = n2;// n1 move
n2 = n3;// n2 move
}
n3 = n1;// n3 -> save last node
n2 = head;// n2 -> left first node
boolean res = true;
// 慢指標從右邊開始 快指標從頭結點開始 一一比較，任何一個為空就停下來
while (n1 != null && n2 != null) {
if (n1.value != n2.value) {
res = false;
break;
}
n1 = n1.next;// left to mid
n2 = n2.next;// right to mid
}
n1 = n3.next;
n3.next = null;
// 將右部分逆序回來
while (n1 != null) {
n2 = n1.next;
n1.next = n3;
n3 = n1;
n1 = n2;
}
return res;
}
public static void printLinkedList(Node head) {
System.out.print("Linked List:");
while (head != null) {
System.out.print(head.value + " ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = null;
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(2);
head.next.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(2);
head.next.next.next.next = new Node(1);
printLinkedList(head);
System.out.print(isPalindrome1(head) + " | ");
System.out.print(isPalindrome2(head) + " | ");
System.out.println(isPalindrome3(head) + " | ");
printLinkedList(head);
System.out.println("=========================");
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/374734.html
標籤：java
上一篇：資料庫學習筆記02