题解 | #判断一个链表是否为回文结构#

时间复杂度O(n), n为链表长度；空间复杂度O(1)。
1 先遍历出链表的长度
2 再反转链表的右半部分
3 比较左右半部分是否相等，即可判断一个链表是否为回文串。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node head = null, p = null;
        for (int i = 0; i < n; ++i) {
            if (head ==  null) {
                head = p = new Node(sc.nextInt());
            } else {
                p.next = new Node(sc.nextInt());
                p = p.next;
            }
        }
        System.out.println(check(head) ? "true": "false");
    }

    private static boolean check(Node head) {  // 故意没有将链表长度传进来
        if (head == null) {
            return false;
        }
        int len = 0;
        Node p = head, end = null;
        while(p != null) {
            len++;
            end = p;
            p = p.next;
        }
        int mid = len - 1 >> 1;
        p = head;
        while(mid > 0) {
            p = p.next;
            --mid;
        }
        reverse(p, null, p.next, end);
        p = p.next; // 右半部分的指针
        Node q = head;  // 左半部分的指针
        while(p != null) {
            if (p.val != q.val) {
                return false;
            }
            p = p.next;
            q = q.next;
        }
        return true;
    }

    private static void reverse(Node left, Node right, Node start, Node end) {
        // in:  left -> start -> ... -> end -> right
        // out: left -> end -> ... -> start -> right
        if (start == null) return;
        Node pre = start;
        Node cur = start.next;
        Node next = null;
        while(cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        start.next = right;
        if (left != null) {
            left.next = end;
        }
    }
}

class Node {
    int val;
    Node next;
    Node(int val) {
        this.val = val;
    }
}