博客

题目：

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例 1：

输入: head = [1,2,3,3,2,1]

输出: true

示例 2：

输入: head = [1,2]

输出: false

提示：

链表 L 的长度范围为 [1, 105]

0 <= node.val <= 9

代码：寻找中间节点 + 反转链表 + 双指针 O(N) O(1)

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode mid = searchMid(head);
        ListNode l = reverse(mid.next);
        mid.next = null;
        return biJiao(head, l);
    }
    public ListNode searchMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    public boolean biJiao(ListNode l1, ListNode l2) {
        while (l1 != null && l2 != null) {
            if (l1.val != l2.val) {
                return false;
            }
            l1 = l1.next;
            l2 = l2.next;
        }
        return true;
    }

}

解题思路：

首先找到链表的中间节点，然后把后半段链表进行反转，然后把两个链表遍历并进行比较就行啦。

注意：

注意前半段链表的最后一个节点的下一个节点要置为空，比较的时候要比较节点的值不要直接比较节点。