LCR 027

题目：LCR 027

解法一：快慢指针 + 反转链表

1. 取中间节点的下一节点，即为链表后半部分。当链表为(1,2,3,4,null)时，取节点3。当链表为(1,2,3,4,5,null)时，取节点4。
2. 反转后半部分链表
3. 前半链表与后半链表同时开始向后遍历，验证回文串
4. 恢复链表

    public boolean isPalindrome(ListNode head) {if (head == null || head.next == null) return true;ListNode slow = head, fast = head;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}ListNode reverse = reverseList(slow.next), node1 = head, node2 = reverse;while (node2 != null) {if (node2.val != node1.val) return false;node2 = node2.next;node1 = node1.next;}reverseList(reverse);return true;}public ListNode reverseList(ListNode head) {ListNode prev = null, curr = head, next;while (curr != null) {next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;