Implement a function to check if a linked list is a palindrome.
Hint
- A palindrome is something which is the same when written forwards and backwards. What if you reversed the linked list?
- Try using a stack.
- Assume you have the length of the linked list. Can you implement this recursively?
- In the recursive approach (we have the length of the list), the middle is the base case: isPermutation(middle) is true. The node x to the immediate left of the middle: What can that node do to check if x -> middle -> y forms a palindrome? Now suppose that checks out. What about the previous node a? If x -> middle -> y is a palindrome, how can it check that a -> x -> middle -> y-> b is a palindrome?
- Go back to the previous hint. Remember: There are ways to return multiple values. You can do this with a new class.
Solution
本题让我们判断一个链表是否为回文链表，由于不能随机访问结点，因此一个直接的思路便是先把所有结点压入一个stack，然后再次遍历链表同时将结点出栈，比较两者的值是否对应相等即可。前面的方法需要遍历两次链表，我们可以进一步优化，利用快慢指针（慢指针1步，快指针2步）找到链表中点后，直接继续遍历后半段即可进行比较。
public static boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
Deque<Integer> stack = new LinkedList<>();
stack.push(head.val);
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
stack.push(slow.val);
}
if (fast.next == null) stack.pop(); // 结点数为奇数时，去掉中间结点
while (slow.next != null) {
slow = slow.next;
if (slow.val != stack.pop()) return false;
}
return true;
}
