Palindrome Linked List

Description

Implement a function to check if a linked list is a palindrome.

Example
Given 1->2->1, return true

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

We are here

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /**
     * @param head a ListNode
     * @return a boolean
     */
    bool isPalindrome(ListNode* head) {
        // Write your code here
        if (!head || !head->next) {
            return true;
        }
        // find middle node
        ListNode* mid = findMid(head);
        // reverse rest list after middle node
        ListNode* rest = reverseList(mid->next);
        // seprate two parts
        mid->next = nullptr;
        // check from begin with reversed rest list to match the palindrome
        return in_isPalindrome(head, rest);
    }
    ListNode* findMid(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    ListNode* reverseList(ListNode* head) {
        ListNode* tail = nullptr;
        while (head) {
            ListNode* tmp = head->next;
            head->next = tail;
            tail = head;
            head = tmp;
        }
        return tail;
    }
    bool in_isPalindrome(ListNode* left, ListNode* right) {
        while (left && right) {
            if (left->val != right->val) {
                return false;
            }
            left = left->next;
            right = right->next;
        }
        return true;
    }
};

Similar problems

x

Tags

x