正视自己的懦弱和无能，克服自己的嫉妒与不甘
—— 24.12.3
234. 回文链表
给你一个单链表的头节点
head，请你判断该链表是否为回文链表
。如果是，返回
true；否则，返回false。示例 1：
输入：head = [1,2,2,1] 输出：true示例 2：
输入：head = [1,2] 输出：false提示：
- 链表中节点数目在范围
[1, 105]内0 <= Node.val <= 9进阶：你能否用
O(n)时间复杂度和O(1)空间复杂度解决此题？
方法一 存入数组双指针
如果单纯的在数组中判断回文数，我们只需定义两个指针，指针1指向数组头结点的位置，指针2指向数组中最后一个元素的位置，遍历迭代指针1和指针2，首先遍历一遍链表，将链表的节点都存入数组中，回文数的定义是从前到后和从后向前占总长度各一半，并且元素值按序相同，所以我们进行遍历迭代指针1和指针2，如果发现二者不相等，则返回false，证明该链表不是回文链表，直到遍历完一遍，中途没有停止返回false，则该链表为回文链表
Java实现
/**
* 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> arr = new ArrayList<Integer>();
ListNode pre = head;
while(pre != null){
arr.add(pre.val);
pre = pre.next;
}
int front = 0;
int back = arr.size() - 1;
while(front < back){
if(!arr.get(front).equals(arr.get(back))){
return false;
}
front++;
back--;
}
return true;
}
}
Python实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
arr = []
while head is not None:
arr.append(head.val)
head = head.next
return arr == arr[::-1]
