Topic describes

// Check whether a linked list is a palindrome list.Copy the code

Answer key

Auxiliary / / / / array will list all the elements in the array list, then set about pointer l and r, circulation has left pointer moves to the right, pointer left/right moving, about to compare the pointer traversal of the element, if not equal directly returns false, / / equal to continue moving, cycle after return true. // Execution time: 14 ms, beating 13.86% of all Java commits // memory consumption: 50.9 MB, Class Solution {public Boolean isPalindrome(ListNode head) {List<Integer> List = new ArrayList<>(); ListNode cur = head; while (cur ! = null) { list.add(cur.val); cur = cur.next; } int l = 0; int r = list.size() - 1; while (l <= r) { if (! list.get(l).equals(list.get(r))) return false; l++; r--; } return true; }}Copy the code
// Find the list midpoint + list reverse // remember [Leetcode] 876. Reverse the list, // we can use problem 876 to find the middle point of the list first, we do not want the right point here, but the left point, // so we need to initialize the fast needle to head next, to do the fast needle, find the middle point after mid. // select mid. Next and reverse the list. // After reversing the list, the mid pointer becomes the head of the reversed list, denoted as rightHead. // Now we have leftHead and rightHead, and we have rightHead and leftHead, and we have rightHead and leftHead, and we have rightHead and leftHead, and we have rightHead and leftHead, and we have rightHead. // 1 -> 2 -> 3 -> 3 -> 2 -> 1 // // // 1 -> 2 -> 3 -> 3 -> 2 -> 1 // //  //leftH mid // 1 -> 2 -> 3 -> 3 -> 2 -> 1 // //leftH mid rightH // 1 -> 2 -> 3 -> 3 <- 2 <- 1 // // Then leftHead and rightHead double pointer moves together. If it's a palindrome list, the pointer elements must be equal, otherwise it's not a palindrome list. // // execution time: 5 ms, beating 58.54% user // memory consumption in all Java commits: 48.3 MB, Class Solution {public Boolean isPalindrome(ListNode head) {ListNode cur = head; ListNode mid = head; while (cur ! = null && cur.next ! = null) { cur = cur.next.next; mid = mid.next; } ListNode rightHead = reverseListNode(mid.next); ListNode leftHead = head; while (leftHead ! = null && rightHead ! = null) { if (leftHead.val ! = rightHead.val) return false; leftHead = leftHead.next; rightHead = rightHead.next; } return true; } public ListNode reverseListNode(ListNode head) { if (head == null || head.next == null) return head; ListNode pre = head; ListNode mid = head.next; ListNode cur = head.next.next; pre.next = null; mid.next = pre; while (cur ! = null) { pre = mid; mid = cur; cur = cur.next; mid.next = pre; } return mid; }}Copy the code