234.回文鏈表2

感覺自己還是有點時間，然后又學了兩種解法。那就一起整理一下。

法一：反轉鏈表后比較

題解看我的這一篇就行（click)

法二：數組+雙指針

思路很簡單，就是用while循環遍歷一下整個鏈表將對應的值復制到數組中，然后定義兩個指針front和back，從前往后和從后往前同時開始，不等就返回false了。

代碼：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {//2.數組+雙指針List<Integer> vals=new ArrayList<Integer>();//將鏈表的值復制到數組中ListNode curr=head;while(curr!=null){vals.add(curr.val);curr=curr.next;}//使用雙指針判斷其是否是回文int front=0;int back=vals.size()-1;while(front<back){if(!vals.get(front).equals(vals.get(back))){return false;}front++;back--;}return true;}
}

法三：遞歸

這個就老好玩了，我以前覺得老難了，因為不理解，也有可能是因為我在這個起步階段，還沒碰到難點，嘿嘿，不管不管。

首先他就是讓你直接到該鏈表的最后一個值，然后在不滿足情況的時候慢慢的往回退。想象一下，你拿著個繩子，繩子下面又掉了個石頭，然后憑著自己的意愿將石頭拋了下去，（感覺這個例子不太好），直到繩子繃緊就是下不去了，嗯，接著你又想收了，然后慢慢的收，一點點扯的這種。但是有條件的。回歸到題目本身，往下放的條件是curr.next不為空，當其為空之后返回其上一個結點。看代碼吧

代碼：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {private ListNode frontPointer;//遞歸函數private boolean recursivelyCheck(ListNode curr){if(curr!=null){if(!recursivelyCheck(curr.next)) return false;if(curr.val!=frontPointer.val)  return false;frontPointer=frontPointer.next;}return true;}public boolean isPalindrome(ListNode head) {//3、遞歸frontPointer=head;return recursivelyCheck(head);}
}

祝你生活愉快~

最近生活還行，你呢？噠噠噠~