LeetCode [234] Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

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

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool isPalindrome(ListNode* head) { ListNode *H1 = new ListNode(0); H1->next = head; ListNode *p1 = H1, *p2 = H1; while(p2 && p2->next){ p1 = p1->next; p2 = p2->next->next; } ListNode *H2 = new ListNode(0), *h2 = p1->next; H2->next = h2; if(!h2) return true; p2 = h2->next; h2->next = NULL; while(p2){ ListNode *next = p2->next; p2->next = h2; H2->next = p2; h2 = p2; p2 = next; } p1 = H1; p2 = H2; while(p2){ if(p1->val!=p2->val) return false; p1 = p1->next; p2 = p2->next; } return true; } };

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 43 44

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public boolean isPalindrome(ListNode head) { if(head==null || head.next==null) return true; if(head.next.next==null) return head.val==head.next.val; ListNode fast = head, slow = head; while(fast!=null && fast.next!=null){ slow = slow.next; fast = fast.next.next; } ListNode prev = slow; ListNode cur = slow.next; ListNode p1 = head; ListNode p2 = null; while(cur!=null){ ListNode next = cur.next; if(next==null) p2 = cur; cur.next = prev; prev = cur; cur = next; } while(true){ if(p1.val!=p2.val) return false; if(p1.next == p2 || p1.next == p2.next) break; p1 = p1.next; p2 = p2.next; } return true; } }