题目描述

编写一个函数，检查输入的链表是否是回文的。

示例 1：

1 2	输入： 1->2 输出： false

示例 2：

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

题解

快慢指针+反转链表

在字符串或者数组题目中判断回文可以选择从中间往两边扩展的方法来验证, 但是链表不行, 因为链表具有单向性, 不能往回遍历.

首先还是先找到中间的节点, 使用快慢指针的方法

然后将后面半段的链表反转, 然后再逐一对比前半段和反转后的后半段链表是否相同

public class jd0206 {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null)
            return true;

        Stack<Integer> stack = new Stack<>();
        ListNode slow = head;
        ListNode fast = head;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode reverseLinked = reverseLinked(slow.next);

        while (reverseLinked!=null){
            if (head.val!=reverseLinked.val)
                return false;

            head = head.next;
            reverseLinked = reverseLinked.next;
        }

        return true;
    }

    // 反转链表
    private ListNode reverseLinked(ListNode head) {
        ListNode pre = head;
        ListNode cur = null;

        while (pre != null) {
            ListNode t = pre.next;
            pre.next = cur;
            cur = pre;
            pre = t;
        }
        return cur;
    }
}