力扣 234. 回文链表

234. 回文链表

请判断一个链表是否为回文链表。
示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路一：

借助一个列表，先遍历链表存下所有结点，然后第二次遍历链表比较列表中的结点

 1 class Solution {
 2     
 3     public boolean isPalindrome(ListNode head) {
 4         ArrayList<ListNode> list = new ArrayList<>();
 5         for(ListNode node = head; node != null; node = node.next){
 6             list.add(node);
 7         }
 8         int i = list.size()-1;
 9         for(ListNode node = head; node != null && i >= 0; node = node.next, i--){
10             if(node.val != list.get(i).val){
11                 return false;
12             }
13         }
14         return true;
15     }
16 }

力扣测试时间为2ms, 空间为43.2MB

复杂度分析：

时间复杂度：遍历了两次链表，所以时间复杂度为O(n)

空间复杂度：O(n)