设计一种方式检查一个链表是否为回文链表。 样例 1->2->1 就是一个回文链表。 挑战 O(n)的时间和O(1)的额外空间。
解题思路：先找到链表中点，然后反转链表后半段，最后分别对比前后两段。 一刷ac。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { /** * @param head a ListNode * @return a boolean */ public boolean isPalindrome(ListNode head) { if(head == null) return true; ListNode mid = findMiddle(head); mid.next = reverse(mid.next); ListNode p1 = head; ListNode p2 = mid.next; while(p2 != null){ if(p1.val == p2.val){ p1 = p1.next; p2 = p2.next; } else{ return false; } } return p2 == null; } public static ListNode findMiddle(ListNode head){ if(head == null || head.next == null) return head; ListNode slow = head; ListNode fast = head.next; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } return slow; } public static ListNode reverse(ListNode head){ if (head == null) return head; ListNode fakehead = null; while(head != null){ ListNode tmp = head.next; head.next = fakehead; fakehead = head; head = tmp; } return fakehead; } }