Description
Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2
Output: false
Example 2:
<pre style="box-sizing: border-box; overflow: auto; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; display: block; padding: 9.5px; margin: 0px 0px 10px; line-height: 1.42857; color: rgb(51, 51, 51); word-break: break-all; word-wrap: break-word; background-color: rgb(245, 245, 245); border: 1px solid rgb(204, 204, 204); border-radius: 4px;">Input: 1->2->2->1
Output: true</pre>
Follow up:
Could you do it in O(n) time and O(1) space?
Solution
Fast-slow-pointer & reverse list, O(n), S(1)
把鏈表拆成兩半，second鏈表做反轉(zhuǎn)，然后比較first和second是否相等（注意長(zhǎng)度可能會(huì)差一位）即可娃承。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode secondHead = slow.next;
slow.next = null;
secondHead = reverse(secondHead);
while (head != null && secondHead != null && head.val == secondHead.val) {
head = head.next;
secondHead = secondHead.next;
}
return head == null || secondHead == null;
}
private ListNode reverse(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverse(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
