Solution to Q234: Determine Palindrome.


  • 0
    Y

    Summary:

    Use reverseList function to reverse the list from the middle of the given linked list.

    Example:

    Suppose we have a linked list 1->2->3->2->0;

    Firstly, reverse the list from the middle. Then we get two lists,

    1. 1->2->3->2->1
    2. 0->2

    Second, compare the two lists from the beginning to half number of the original list. If there is a difference, return False. Otherwise, in the end, return True.

    NOTE:

    1. We need to consider odd length or even length.
    2. This Algorithm runs in O(n) time and O(1) space.
    class Solution {
    public:
        ListNode* reverseList(ListNode* head){
            if(head == NULL)
                return NULL;
            if(head->next == NULL)
                return head;
    
            ListNode* curr = head->next;
            ListNode* pre = head;
            ListNode* post = head->next->next;
            pre->next = NULL;
            while(curr != NULL){
                curr->next = pre;
                pre = curr;
                curr = post;
                if(post != NULL)
                    post = post->next;
    
            }
            return pre;
        }
    
        bool isPalindrome(ListNode* head) {
            int length = 0;
            ListNode* traversal = head;
            while(traversal != NULL){
                traversal = traversal->next;
                length++;
            }
            traversal = head;
            int half = length / 2;
    
            if(length % 2 == 0){
                while(half > 0){
                    traversal = traversal->next;
                    half--;
                }
                ListNode* newHead = reverseList(traversal);
    
                half = length / 2;
    
                while(half > 0){
                    if(newHead->val != head->val)
                        return false;
                    newHead = newHead->next;
                    head = head->next;
                    half--;
                }
                return true;
            }
            else{
                while(half > 0){
                    traversal = traversal->next;
                    half--;
                }
                traversal = traversal->next;
                ListNode* newHead = reverseList(traversal);
    
                half = length / 2;
    
                while(half > 0){
                    if(newHead->val != head->val)
                        return false;
                    newHead = newHead->next;
                    head = head->next;
                    half--;
                }
                return true;
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.