Description
Given a singly linked list, determine if it is a palindrome.
Example
Example 1:
1 2
| Input: 1->2 Output: false
|
Example 2:
1 2
| Input: 1->2->2->1 Output: true
|
Follow up:
Could you do it in O(n) time and O(1) space?
Solution
- Move: fast pointer goes to the end, and slow goes to the middle.
- Reverse: the right half is reversed, and slow pointer becomes the 2nd head.
- Compare: run the two pointers head and slow together and compare.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
|
class Solution { public boolean isPalindrome(ListNode head) { ListNode fast = head, slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } if (fast != null) { slow = slow.next; } slow = reverse(slow); fast = head; while (slow != null) { if (fast.val != slow.val) { return false; } fast = fast.next; slow = slow.next; } return true; }
public ListNode reverse(ListNode head) { ListNode prev = null; while (head != null) { ListNode next = head.next; head.next = prev; prev = head; head = next; } return prev; } }
|