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: Using Stack or Vector

Time complexity of above method is O(n), but it requires O(n) extra space. Following methods solve this with constant extra space.

    bool isPalindrome(ListNode* head) {
        vector<int> arr;        
        ListNode *temp = head;
        while(temp) {
            arr.push_back(temp->val);
            temp = temp->next;
        }

        for (int i=0; i<arr.size()/2; i++) {
            if (arr[i] != arr[arr.size()-i-1]) return false;
        }

        return true;
    }

Solution 2: By reversing the list

This method takes O(n) time and O(1) extra space.

  1. Get the middle of the linked list.
  2. Reverse the second half of the linked list.
  3. Check if the first half and second half are identical.
  4. Construct the original linked list by reversing the second half again and attaching it back to the first half
bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;

    ListNode *temp = head;
    ListNode *middle = head;
    while (temp->next && temp->next->next) {
        temp = temp->next->next;
        middle = middle->next;
    }

    middle = reverse(middle);

    temp = head;
    while(temp && middle) {
        if (temp->val != middle->val) return false;
        temp = temp->next;
        middle = middle->next;
    }
    return true;
}

ListNode* reverse(ListNode *head) {
    if (!head || !head->next) return head;

    ListNode *rest = reverse(head->next);
    head->next->next = head;
    head->next = NULL;
    return rest;
}

Solution 3: Using Recursion

Use two pointers left and right. Move right and left using recursion and check for following in each recursive call.

  1. Sub-list is palindrome.
  2. Value at current left and right are matching.

The idea is to use call stack as container. The idea is to use function call stack as container. Recursively traverse till the end of list. When we return from last NULL, we will be at last node. The last node to be compared with first node of list.

Note: the key is how to move left and right pointer.

bool isPalindrome(ListNode* head) {
    return isPalindromeUtil(&head, head);
}

bool isPalindromeUtil(ListNode **left, ListNode *right) {
   /* stop recursion when right becomes NULL */
   if (!right) return true;

   /* If sub-list is not palindrome then no need to
       check for current left and right, return false */
   if (isPalindromeUtil(left, right->next) == false) return false;

   /* Check values at current left and right */
   bool isp = (right->val == (*left)->val);

   /* Move left to next node */
   *left = (*left)->next;

   return isp;
}

results matching ""

    No results matching ""