234. Palindrome Linked List 发表于 2021-12-22 Stack1234567891011121314151617181920212223242526272829303132class Solution { public boolean isPalindrome(ListNode head) { // d * * * * * // f f f f // s s s s // d * * * * * * // f f f f // s s s s ListNode dummyHead = new ListNode(); dummyHead.next = head; Stack<Integer> stack = new Stack<>(); ListNode fast = dummyHead, slow = dummyHead; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast != null) { stack.push(slow.val); } } ListNode curr = slow.next; while (curr != null && curr.val == stack.peek()) { stack.pop(); curr = curr.next; } return stack.isEmpty(); }} Linked List123456789101112131415161718192021222324252627282930313233343536373839404142434445464748class Solution { public boolean isPalindrome(ListNode head) { if (head.next == null) { return true; } // d -> 1 -> 2 -> 3 // f // s // d -> 1 -> 2 -> 3 -> 4 // f // s ListNode dummyHead = new ListNode(-1, head); ListNode fast = dummyHead, slow = dummyHead; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } ListNode rightHead = slow.next; slow.next = null; ListNode reversedRightHead = reverse(rightHead); ListNode nodeA = head, nodeB = reversedRightHead; while (nodeB != null) { if (nodeB.val != nodeA.val) { return false; } nodeB = nodeB.next; nodeA = nodeA.next; } return true; } private ListNode reverse(ListNode node) { ListNode pre = null; while (node != null) { ListNode next = node.next; node.next = pre; pre = node; node = next; } return pre; }} Reference234. Palindrome Linked List剑指 Offer II 027. 回文链表