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
本題讓我們判斷一個(gè)鏈表是否為回文鏈表绘雁，由于不能隨機(jī)訪問結(jié)點(diǎn)症歇，因此一個(gè)直接的思路便是先把所有結(jié)點(diǎn)壓入一個(gè)stack顶瞒，然后再次遍歷鏈表同時(shí)將結(jié)點(diǎn)出棧兴枯，比較兩者的值是否對應(yīng)相等即可挽牢。前面的方法需要遍歷兩次鏈表鳍侣，我們可以進(jìn)一步優(yōu)化俺附，利用快慢指針（慢指針1步矛纹，快指針2步）找到鏈表中點(diǎn)后，直接繼續(xù)遍歷后半段即可進(jìn)行比較霜医。
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(); // 結(jié)點(diǎn)數(shù)為奇數(shù)時(shí)，去掉中間結(jié)點(diǎn)
while (slow.next != null) {
slow = slow.next;
if (slow.val != stack.pop()) return false;
}
return true;
}
