/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ publicclassSolution{ publicbooleanisPalindrome(ListNode head){ // Note: the input will be changed, which is considered as a bad practice ListNode dummy = new ListNode(0); dummy.next = head; ListNode slow = dummy; ListNode fast = dummy; // The above 4 lines can be replaced by the following 3 lines // if (head == null) return true; // ListNode slow = head; // ListNode fast = head.next; // find the middle point while (fast != null && fast.next !=null) { slow = slow.next; fast = fast.next.next; } // reverse the latter half, then compare the value from two ends to the middle point ListNode end = reverseLinkedList(slow.next); while (head != null && end != null) { if (head.val != end.val) { returnfalse; } else { head = head.next; end = end.next; } } returntrue; } public ListNode reverseLinkedList(ListNode head){ ListNode prev = null; while (head != null) { ListNode next = head.next; head.next = prev; prev = head; head = next; } return prev; } }