234. 回文链表（数据结构系列）

234. 回文链表

• 题目
• 解题思路
• 代码

题目

请判断一个链表是否为回文链表。

解题思路

判断一个链表是不是回文链表，一般都用双指针，从两端向中间收缩。
最简单的思路就是反转单链表，如果反转后的链表和原来的链表相同，那就是回文链表。可以不用显式的反转链表，借助后序遍历，同样能达到倒叙遍历链表的目的。

还可以用快慢指针来优化空间复杂度，即反转链表的一半，只要比较前一半和后一半是否相等即可。

代码

基础版本

class Solution {
    ListNode left;
    public boolean isPalindrome(ListNode head) {
        left=head;
    return  traverse(head);
    }

    public boolean traverse(ListNode right){
        if(right==null){
            return true;
        }
        boolean res=traverse(right.next);
        //后序遍历写在这
        res=res&&(right.val==left.val);
        left=left.next;
        return res;
    }
}

优化空间复杂度版本

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow;
        ListNode fast;
        fast = slow = head;

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

        if (fast != null) {//快指针已经停止了，但是没到null，证明链表为奇数
            slow = slow.next;//因为要从slow开始反转，所以slow还要向前走一步
        }

        //left、right指针用来比较反转后二者是否相同
        ListNode left = head;
        ListNode right = reverse(slow);//right从反转后的头节点开始

        while (right != null) {
            if (left.val != right.val) {
                return false;
            }
            left = left.next;
            right = right.next;
        }

        return true;


    }

    /* 反转以head为头的链表，返回反转后的头节点*/
    ListNode reverse(ListNode head) {
        /*
        比如 1->2->3->4->3->2->1从右边的3反转后应该为
        1->2->3->4  1->2->3->null
         */
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre=cur;
            cur = next;
        }

        return pre;
    }
}