LeetCode 234.回文链表

题目：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

思路：注意链表节点个数为奇数时，2->3之间的连接没有断

代码：

class Solution {public boolean isPalindrome(ListNode head) {ListNode mid = middleNode(head);ListNode head2 = reverseList(mid);// 2 -> 3 的连接没有断while (head2 != null) {if (head.val != head2.val) { // 不是回文链表return false;}head = head.next;head2 = head2.next;}return true;}// 反转链表private ListNode reverseList(ListNode head) {ListNode pre = null, cur = head;while (cur != null) {ListNode nxt = cur.next;cur.next = pre;pre = cur;cur = next;   }return pre;}// 寻找链表中间节点private ListNode middleNode(ListNode head) {ListNode slow = head, fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}
}

性能：

时间复杂度o（n）

空间复杂度o（1）