leetcode-234 回文链表

题目描述：请判断一个链表是否为回文链表。你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

代码实现

递归实现

class Solution {
    public boolean isPalindrome(ListNode head) {
        //1. 判空
        if (head == null || head.next == null) {
            return true;
        }

        //2. 遍历计算链表长度
        ListNode node = head;
        int len = 0;
        while (node != null) {
            len++;
            node = node.next;
        }

        //3. 寻找中间节点
        node = head;
        int subLen = len / 2 + len % 2;
        while (subLen-- != 0) {
            node = node.next;
        }

        //4. 反转右半链表区间剩余节点
        ListNode subHead2 = reverse(node);
        ListNode subHead1 = head;

        //5. 分别对比左链表区间元素与右链表区间元素
        while (subHead1 != null && subHead2 != null) {
            if (subHead1.val != subHead2.val) {
                return false;
            }
            subHead1 = subHead1.next;
            subHead2 = subHead2.next;
        }
        return true;
    }

    /**
     * 链表反转
     *
     * @param head 链表头节点
     * @return 返回反转后的链表头节点
     */
    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}