leetcode234. 回文链表

leetcode234. 回文链表

1.题目描述：

给你一个单链表的头节点head，请你判断该链表是否为回文链表。如果是，返回true；否则，返回false。进阶：用O(n)时间复杂度和O(1)空间复杂度解决此题。

 2.使用集合：用集合存储节点值后再判断，代码较简单如下。

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head.next == null) return true;
        List list = new ArrayList<>();
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        for(int i = 0;i < list.size() / 2;i++){
            if(list.get(i) != list.get(list.size() - i - 1)) return false;
        }
        return true;
    }
}

3.进阶：使用快慢指针找到中间节点，将之后的链表反转并与之前的相比，思路直接见代码。

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head.next == null) return true;
        ListNode l1 = head;//慢指针
        ListNode l2 = head.next;//快指针
        while(l2.next != null && l2.next.next != null){//必须这么写否则下次循环很容易空指针
            l1 = l1.next;
            l2 = l2.next.next;
        }
        ListNode l3 = l1;
        //找到偶数个左边的最末节点，奇数个的中间节点前一个节点
        //对于反转后对比，始终对比第一个节点到l1节点，所以奇偶无影响
        ListNode temp;
        ListNode pre = null;
        while(l3 != null){
            temp = l3.next;
            l3.next = pre;//注意这里第一次循环后head链表就被一分为二了
            pre = l3;
            l3 = temp;
        }//将l1后的链表反转
        ListNode temp1 = head;//对比第一个节点到l1节点
        while(temp1 != null){
            if(pre.val != temp1.val) return false;
            pre = pre.next;
            temp1 = temp1.next;
        }
        return true;
    }
}

 4.递归：略