Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
Solution:
1. /*
2. * Definition for singly-linked list.
3. * public class ListNode {
4. * int val;
5. * ListNode next;
6. * ListNode(int x) { val = x; }
7. * }
8. /
9. public class Solution {
10. public boolean isPalindrome(ListNode head) {
11. if (head == null || head.next == null)
12. return true;
13. 14. // step 1. cut the original list to two halves
15. ListNode prev = null, slow = head, fast = head, l1 = head;
16. 17. while (fast != null && fast.next != null) {
18. prev = slow;
19. slow = slow.next;
20. fast = fast.next.next;
21. }
22. 23. prev.next = null;
24. 25. // step 2. reverse the 2nd half
26. ListNode l2 = (fast == null) ? reverse(slow) : reverse(slow.next);
27. 28. // step 3. compare the new two halves
29. while (l1 != null && l2 != null) {
30. if (l1.val != l2.val)
31. return false;
32. 33. l1 = l1.next;
34. l2 = l2.next;
35. }
36. 37. return true;
38. }
39. 40. // helper function: reverse a list
41. ListNode reverse(ListNode head) {
42. ListNode prev = null, curr = head, next = null;
43. 44. while (curr != null) {
45. next = curr.next;
46. curr.next = prev;
47. prev = curr;
48. curr = next;
49. }
50. 51. return prev;
52. }
53. }