判断单链表回文的三种方法

上海自来水来自海上，中山诸罗茶罗诸山中。非常有意境的句子，正着读倒着读都是一个意思。非常对陈，强迫症患者福音。本文分享了基于单链表判断回文的三种方法。所有源码均已上传至github： 链接

基于数组

用数组存储链表前半段的值，使用快慢指针法来进行截取。

但是这种数组的倒序插入比较费时。

小技巧 ：一直使用node.add(0,slow.data)相当于倒序插入

private boolean isPalindromeByArray(Node node) {
        if (null == node || null == node.next) return true;
        List<Integer> nodeList = new ArrayList<>();
        Node fast = node;
        Node slow = node;
        nodeList.add(0, slow.data);
        while (null != fast.next && null != fast.next.next) {
            fast = fast.next.next;
            slow = slow.next;
            nodeList.add(0, slow.data);
        }
        Node curNode = slow;
        if (null != fast.next) {
            curNode = slow.next;
        }
        int index = 0;
        while (null != curNode) {
            if (curNode.data != nodeList.get(index)) {
                return false;
            }
            curNode = curNode.next;
            ++index;
        }
        return true;
    }复制代码

基于栈

和数组的思想是一样的，只不过存储方式换成了栈，然后不断地出栈和链表后半段比较即可。这种方式比较高效。

private boolean isPalindromeByStack(Node node) {
        if (null == node || null == node.next) return true;
        Stack<Integer> stack = new Stack<>();
        Node fast = node;
        Node slow = node;
        stack.push(slow.data);
        while (null != fast.next && null != fast.next.next) {
            fast = fast.next.next;
            slow = slow.next;
            stack.push(slow.data);
        }
        if (null != fast.next) {
            slow = slow.next;
        }
        Node curNode = slow;
        while (null != curNode) {
            if (curNode.data != stack.pop()) {
                return false;
            }
            curNode = curNode.next;
        }
        return true;
    }复制代码

原地链表法