一、回文鏈表

234.回文鏈表

兩種解法

解法1：時間復雜度O(n) 空間復雜度O(n)

遍歷鏈表，計算鏈表長度，創建同樣長度大小的數組，用數組存儲鏈表中所有元素，之后雙指針遍歷鏈表，一個從頭開始，一個從尾開始，比較元素是否相等；

class Solution {public boolean isPalindrome(ListNode head) {ListNode curr = head;int len = 0;if(head.next == null){return true;}while(curr != null){len++;curr = curr.next;}//重置currcurr = head;int[] nums = new int[len];for(int i = 0;i < nums.length;i++){if(curr != null){nums[i] = curr.val;curr = curr.next;}else{break;}}for(int i = 0,j = nums.length - 1;i < j;i++,j--){if(nums[i] != nums[j]) return false;}return true;}
}

注意??：求完鏈表長度后，記得重置curr；?

解法2：時間復雜度O(n) 空間復雜度O(1)

快慢指針法（??）

定義兩個指針，快指針fast，慢指針slow，初始指向頭結點，只要fast != null && fast.next != null，那么慢指針每次移動一個結點，快指針每次移動兩個結點；直到fast不滿足條件，此時，慢指針指向中點（鏈表個數為奇數），或者中點偏右的位置（鏈表個數為偶數）；

之后，反轉后半部分鏈表，然后比較前后兩部分的數值，相等，則為回文鏈表，否則不是；

使用快慢指針法找到鏈表的中點的原理：

快指針的速度是慢指針的 2 倍，所以當快指針走完全程時，慢指針剛好走了一半。

慢指針走過的路程為 x，那么快指針就是2x，2x = len，則x = 1/2 len；

class Solution {public boolean isPalindrome(ListNode head) {//快慢指針ListNode slow = new ListNode();ListNode fast = new ListNode();if(head == null || head.next == null){return true;}slow = head;fast = head;while(fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;}//若鏈表為奇數個 此時slow指向中間點//若鏈表為偶數個 此時slow指向中間偏右的結點//反轉后半部分鏈表ListNode pre = null;ListNode curr = slow;while(curr != null){ListNode temp = curr.next;curr.next = pre;pre = curr;curr = temp;}//此時pre指向反轉后鏈表的頭部//比較前后兩部分鏈表ListNode pA = head;ListNode pB = pre;while(pB != null){if(pA.val != pB.val){return false;}pA = pA.next;pB = pB.next;}return true;}
}

注意??：在比較前后兩部分鏈表時，while中的判斷條件只能是pB != null；

如果是pA != null，那么當鏈表個數為偶數時：1 2 3 4；

slow最后指向3，后半部分反轉后，整體鏈表結構為：

前：1 --> 2 -->3 --> null? ? ? ?

后：4 ---> 3 --> null

pA遍歷的是前半部分的鏈表，pB遍歷后半部分，當pB指向null時，pA指向3，不為空，進入循環，pB.val就會報錯：空指針異常；?