1. 題目
給你一個單鏈表的頭節點 head ，請你判斷該鏈表是否為回文鏈表。如果是，返回 true ；否則，返回 false 。
示例 1：
輸入：head = [1,2,2,1]
輸出：true
示例 2：
輸入：head = [1,2]
輸出：false
2. 題解
/*** 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) {List<Integer> vals = new ArrayList<Integer>();//將鏈表的值復制到數組中ListNode currentNode = head;while(currentNode != null){vals.add(currentNode.val);currentNode = currentNode.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;}
}
3. 解析
官方回答：回文鏈表
-
1-4. ListNode currentNode head; while(currentNode != null) {…} - 將頭節點賦值給變量currentNode，然后進入循環直到currentNode為null。
-
5.vals.add(currentNode.val); - 每次迭代時，都會將當前節點的值添加到列表vals中。
6-7: front = 0; back = vals.size() - 1; - 初始化兩個指針：前指針front和后指針back，分別從數組兩端開始。 -
9-12. if (!vals.get(front).equals(vals.get(back))) { return false; } front++; back–; - 然后進入循環直到front >= back。如果前指針對應的值和后指針對應的值不相等，則返回false（因為這意味著鏈表不是回文）。否則，將前指針加1并減小后指針以向中間移動。
-
13.return true; - 如果while循環結束時沒有找到兩個位置上的元素不相同，那么該函數返回true，表示鏈表是回文的。
-
這段代碼的時間復雜度為O(n)，其中n是單鏈表中的節點數，因為我們需要遍歷整個列表一次來將值復制到vals中。空間復雜度也為O(n)，因為我們在創建一個新的ArrayList來存儲所有的值。
