234. Palindrome Linked List

• Link: https://leetcode.com/problems/palindrome-linked-list/

Question

Given the head of a singly linked list, return true if it is a

palindrome

or false otherwise.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

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

Approach 1: Brute Force

Intuition

• Using stack data structure as we need to compare the linkedlist with its reverse.
• Stack is Last In First Out.

Algorithm

1. Initialize a stack<int> s & ListNode* curr = head
2. Loop through the LL using curr
   1. Push the curr->val to s
   2. curr = curr->next
3. Assign curr = head
4. Loop through the LL using curr
   1. If curr->val != s.top() return false
   2. Else s.pop()
   3. curr = curr->next
5. Return true

Code

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack<int> s;
        ListNode* curr = head;

        while (curr) {
            s.push(curr->val);
            curr = curr->next;
        }

        curr = head;
        
        while (curr) {
            if (curr->val != s.top()) return false;
            s.pop();
            curr = curr->next;
        }

        return true;
    }
};

Complexity Analysis

• Time Complexity: $O(2N)=O(N)$
• Space Complexity: $O(N)$ (stack space)

Approach 2: Optimal

• Reversing the 2nd half of the LL then comparing

Algorithm

1. Find the middle of the linked list using floyds tortoise hare algorithm
2. Reverse the second half
3. curr1 for first half, curr2 for second half
4. Loop through the LL till curr2 exists
   1. If curr1->val != curr2->val
      1. reverse the 2nd half again & return false
   2. else curr1 = curr1->next
   3. curr2 = curr2->next
5. Reverse the LL again
6. Return true

Code

class Solution {
public:
    ListNode* reverseLL(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* newHead = reverseLL(head->next);
        head->next->next = head;
        head->next = NULL;
        return newHead;
    }

    bool isPalindrome(ListNode* head) {
        // Edge case for size of LL = 0 or 1
        if (head == NULL || head->next == NULL) return true;

        ListNode* fast = head;
        ListNode* slow = head;

        while (fast && fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }

        ListNode* newHead = reverseLL(slow->next);

        ListNode* curr1 = head;
        ListNode* curr2 = newHead;

        while (curr2) {
            if (curr1->val != curr2->val) {
                reverseLL(newHead);
                return false;
            }
            
            curr1 = curr1->next;
            curr2 = curr2->next;
        }

        reverseLL(newHead);
        return true;
    }
};

Complexity Analysis

• Time Complexity: $O(\frac{N}{2}+\frac{N}{2}+\frac{N}{2}+\frac{N}{2})=O(2N)=O(N)$
• Space Complexity: $O(1)$