如何判断一个单链表是否为回文串？

前情

这道题是极客时间专栏数据结构与算法之美《06 | 链表（上）：如何实现LRU缓存淘汰算法?》里面的一道思考题，同时也是leetcode上的一道题目，原题为：https://leetcode.com/problems/palindrome-linked-list/

由于我在算法方面的基础比较薄弱，所以直接去看了别人的解决方法，也花了好一会才看懂，加上照着敲一遍代码，跑debug 最终才完全理解了这种解法。

思路

使用快慢两个指针找到链表中点，慢指针每次前进一步，快指针每次前进两步。在慢指针前进的过程中，同时修改其 next 指针，使得链表前半部分反序。最后比较中点两侧的链表是否相等。

代码

里面的注释都是我在思考过后补充上去的，相信大家理解了之后再删掉注释也会感觉豁然开朗。

• 我自己给ListNode使用了builder模式，方便测试的时候输入数据（其实不算是严格的builder模式，真正的builder是返回对象this，这里是返回了next的引用）

• 我的注释可能影响你的思考，可以尝试忽略我的注释或者删掉，自己思考

/**
 * Given a singly linked list, determine if it is a palindrome.
 */
public class PalindromeLinkedList {

    // solution
    static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        ListNode prev = null;
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            // 每次跳两个 变相控制了循环的次数，相当于除2
            fast = fast.next.next;
            // 临时变量 暂存
            ListNode next = slow.next;
            // 一开始prev为空时：slow变成了头节点；到后面就是把本来在prev的元素变成它的next
            slow.next = prev;
            prev = slow;

            slow = next;
        }
        // 循环结束 prev就是链表前半部分反序后的链表，slow就是原链表的后半部分

        // 链表节点为偶数时刚好除尽，为奇数时这里的fast就是最后一个节点
        // 节点个数为奇数时则不用比较中间节点 所以这里.next跳过了中间节点
        if (fast != null) {
            slow = slow.next;
        }

        // 依次比较，如果有不同直接返回false
        while (slow != null) {
            if (slow.val != prev.val) {
                return false;
            }
            slow = slow.next;
            prev = prev.next;
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode('a');
        head.next(new ListNode('b')).next(new ListNode('a'));
        System.out.println(head);
        System.out.println(isPalindrome(head));
    }
}

class ListNode {
    char val;
    ListNode next;

    public ListNode(char val) {
        this.val = val;
    }

    // builder mode
    ListNode next(ListNode next) {
        this.next = next;
        return next;
    }

    @Override
    public String toString() {
        return "{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}

运行结果